I've found a workaround for this issue. It is absolutely not a fix, but it will allow you to backup your virtual machines using Time Machine, and prevent Parallels from disabling this.
What you want to do is set up what's called a "fixed path inclusion" for each of your virtual machines. This type of inclusion requires root to add or remove, and Parallels cannot override it.
To do this:
Open
/Utilities/Terminal
Enter
sudo tmutil removeexclusion -p "</path/to/VM.pvm>"
For instance:
sudo tmutil removeexclusion -p "/Users/you/Documents/Parallels/Windows.pvm"
Go back into Parallels and take a look at the backup checkbox. It should be unchecked, even after rebooting your VMs. Parallels is still setting the exclusion by metadata, but it is being overwritten by the explicit fixed path inclusion time machine has for that directory.
It appears you'll need to do this for each VM (.pvm). I tried including the entire Parallels directory and it did not override the exclusions, so apparently it's not recursive. You will also need to do it again if you rename your VMs, as the exclusion applies only to that exact path and filename.
Again, this is not a fix for this issue. Parallels is still reverting the exclusion, we're just overriding it. It will at least let you back up all your VMs until Parallels fixes this issue.
Last edited: Aug 30, 2013