In our demo room I still have V3.0 Contact Store installed and I definitely can't play the wavs - I've installed almost every codec pack I could find and it still wouldn't work.
Upgrading Contact Store from 3.0 to 3.1 was a right pain re. MSDE! I seem to rememeber I had to rename the folder where the CS error msg was appearing then changing it back after the install.
Documentation on the upgrade procedure is awful - I think they should really document how the process works from what is actually stored in the DB - and installers should understand SQL, because a lot of people don't!
Fortunately not seen your problem so can't really offer any help, but it seems like an odd one. If you still have all your recordings (wav and xml files) you could always manually add it to the DB and then it comes up in the searches - just have CS make a normal recording, note the number it creates the xml and wav file. Then rename one of your previous xml and wav files that you can't access anymore (if you don't know which wav it is - you may need to look in the xml file and work out which one it is), then add it all into the DB and then you should be able to listen to it again! Of course, playing the wav file would be far simpler!!