Yes... you could restore back to any available time machine backup.
However, I think that might be a drastic fix to your problem. The uninstaller in the Parallels install package seems reasonably thorough, and all that would be left are the VM files which are easily identifiable and delete-able. Might be a much simpler solution...