2 more points:
*I am IT professional, not an average consumer.
*Also, the card that s7 doesn't recognize anymore is SDXC, it recognizes non XC (16gb) card. Currently I don't have any other cards to try.
I found the solution after extensive search - downloaded Formatter from sdcard.org/downloads and performed OVERWRTIRE format. The key here was the long format. It's possible the Windows long format (e.g. uncheck quick) would have done it as well but I didn't try it.
Nice investigative work! Thanks for sharing your findings as well!