That's odd. Go to /Library/Preferenes and look for com.apple.TimeMachine.plist. Hit spacebar to quick-look it (if you have xCode or BBedit installed, you can just open it in one of those). Look for a key called "IncludeByPath". This lists all fixed path inclusions (which should be created when you use removeexclusion -p).
Basically. look for something like this (should be near the bottom of the plist
<key>IncludeByPath</key>
<array>
<string>/Volumes/Additional Data/Parallels VMs External/Mac OS X Lion.pvm</string>
Are you seeing an entry like this in your plist?