I had a similar problem:
I used two 64 Gb cards working flawlessly for a year or so.
Then all of a sudden the same problem (like you had) with both cards.
I tried everything, and I mean everything(!) - all formats, all my files which worked fine previously. All firmwares, Whatever you can imagine in your wildest dream.
I guess I spent 20 hours or so of my time on this frustrating process.
Miraculously I managed to force to work only one of these cards - now in fat32 format only.
It does work after the cold start without forced rescan again.
Tomorrow I am buying one more card of different brand - to try my luck again and probably to spend 20 hours of my time on it again.
And I am buying Cowon PLENUE 1 128Gb, they say it has the stable firmware with very few glitches and bugs.
And having 128Gb on board I hopefully won't have to spend my time on cards but just listen to music...