Backup of Citrix Presentation servers with Backup Exec 12.5

First of all let me preface this with:  I am not a Citrix guru!  I know enough to be dangerous.  With that said, I *do* know that since using Citrix and Backup Exec for several years...at some point we have lost the capability to actually restore a presentation server with BE.  I know it used to work, but now here we are...I understand that it supposedly is not a supported method.

I have real issues with that...but discussing those issues would be counter-productive.

There *must* be a way...

We are not yet dealing with the virtual world...we're getting there soon (I hope), but not yet.  We do NOT want to deal with Xen!

I have heard rumors of a couple of ways that people are dealing with this problem.

We have Backup Exec 12.5
We have Altiris Deployment Server 6.9
Citrix 4.5 (Farm of 3 presentation servers, 1 licensing server, 1 Citrix Gateway)
Active Directory 2003 environment

From what we have been told, it is only the presentation servers that present the challenge.

Given what we have on hand, is there an acceptable method to recover Citrix Servers in a Disaster?

If we do NOT have what we need (excepting Xen) what product will get us there for the least cost outlay?

I'm open to discussion...what are you guys doing to achieve either outright Backup/Restore or automated re-deployment of a Citrix PS?