I have the same issue... I thought that my VM was getting backed up because I didn't tick the do not backup with Time Machine box in Parallels 9. My Computer crashed and guess what my VM was not backed up... After hours of recreating the VM I realize that every time I untick the box it somehow reticks itself after a boot up of the VM or a restart of Parallels.
The option to sudo tmutil removeexclusion -p the .pvm file is useless (seen in a kb here) and The .pvm is not excluded in the graphical of Time Machine.
I see this thread has been going on for a while and the fact that there are no solutions is quite mind boggling...
On friday 18yh, a very good Indian technician from Parallels, called Manoj, fixed it via remote access.