I'm running Parallels, and I've started using Spaces again recently. However, even though I've limited parallels to only running in one space (in coherence mode), the windows taskbar is showing in ALL spaces. This is a bit confusing because as soon as i click on it, it takes me to the parallels space. The only work-around I can find is to hide the taskbar, but this is not ideal in any way.
This might not be ideal for you, but I would set your VM as full screen and press CTRL+ALT (it will make your dock and the bar on top of the screen visible, and you can open windows over it).