I would disagree. Neither Parallels nor VM Fusion were "compatible" with Time Machine in the way you described. The psuedo-disc was always backed up in its entirety regardless of the magnitude of the changes. This has been the case in all the versions of both Parallels and VM Fusion. They both have recommended omitting the psuedo-disc in order to conserve space on a Time Machine backup drive.
There is no workaround.
Windows is a entire operating system and programs inside, it's quite large I would assume with all the snapshots, for TM to save multiple changes of that would likely fill the TM drive.
Anyway that's just a guest.
The files in VMFusion for other operating systems are just that, files, just very larger ones.
What you can do is get another external drive equal too or larger than your internal boot drive, use Carbon Copy Cloner to clone the internal to the external (include the Lion Recovery Partition)
Leave it disconnected and update it (no archiving) once in awhile, you can hold the option key and boot from this external drive just like before if you should ever need to do so. Also you can erase and reverse clone onto the internal drive or replace files etc.
Just no Filevault or Bootcamp, if you need to clone bootcamp, use Winclone.