I went a different route – let Windows run CheckDisk for the SDXC card. Indeed it found some errors (…why the hell!..) and fixed them. After that I inserted the card into the Clip+ again. And again database refreshing lasted more than three hours – a good sign. Now the player seems to work fine again, without any hickups. Neither did it stumble across any missing tracks; the display still shows a number of 5873 files, and the Clip+ plays them all so far (in shuffle mode), even the ones in the high 5000s.
BTW, a simple way of formatting a (micro)SDXC card to FAT32 is to use a Mac (that’s what I did initially).