i suggest , two backups
1 all the O.S. an configurations with a clone tool like ghost(good), acronis (the best), clonezilla (the free).
2 and of course your typical backup of data or application with any tool you have (tivoli, hp Dataprotector, veritas, tar, CD, etc.
PD : if you use Active Directory, and you will gonna make a change in a server like exchange , you must consider backup your AD controllers
I agree to the above solution.
If you have a unix server. take an image dump along with Cold backup of the data on the server.
if you have database on the server, make sure the cold backup is performed with database shut down while backup is fired.