Fusion isn't entirely different - just that it doesn't seem to throw as much around. VMWare also puts an uninstaller on its Fusion disk image. My assumption is that virtualization products do need to put stuff in places other than /Applications to provide the functionality they offer.
I'd recommend trying Fusion out. In my experience it's faster - proboably because it does away with all the pointless 'thinks it's pretty but actually is just childish' stuff in Parallels.
A rule of thumb with removing applications is always use the uninstaller if there is one. For Adobe/Macromedia stuff that counts double.
I was able to uninstall but with errors. When VMFusion starts the virtual machine , on the Windows boot screens it shows two options -PAralles and XP pro... Now I have to choose manually XP since Paralles option gives error.