The only way to restore the complete server as far as I am aware is to have a full backup of your VMDK and VMX files, there is a way of doing that with Backup Exec and the RALUS agent, i can give you the link if you are really interested.
Your suggestion of rebuilding and restoring is the only way In know of using system recovery.
Once the server is rebuilt i see no reason why you cannot install the system recovery agent and restore completely over the top of the rebuilt server. Haven't tried it mind you, but that is what I would try without a VMDK backup.