I have a similar issue:
I have a Windows 7 VM on Parallels 8 current release.
I had Office 2003 installed
I uninstalled Office 2003 and installed Office 2010
When I do a "get info" on a office file such as a DOCX, or ICS, etc. and I click on Open with I still have the option for the uninstalled Office 2003 app and sometimes the Office 2010 option is completely missing (even if I fix the association and path to the program in windows 7).
Where is Parallels and OS X getting this info from? I need to go clean them up but I have no idea where the list of programs is stored on OS X. I fixed the association for ICS on Windows and so when I click on it in Windows Explorer it works fine, but when I click on it in OS X Finder, it still tries to open outlook 2003 which doesn't exist any more. This tells me OS X/Parallels is not using the windows associations directly but instead may have copied them at some point and now they are corrupt/invalid and I can't figure out how to delete them.