It sounds like Time Machine doesn't backup everything on Mac Server:
http://derflounder.wordpress.com/2010/03/02/restoring-mac-os-x-server-from-time-machine/
So what options do I have? Ideally I'd like a backup that I can restore on another Mac Mini and have it up and running instantly. Carbon Copy Cloner sounds like it should work, but I didn't see anything on their site that said it would definitely backup Mac Server (or I missed it).
Does anyone have a recommendation on what to do?
Best Answer
Yes pretty much anything that can do a boot-able backup of Mac OS X, should be able to do a back up of Mac OS X server. There are very few differences between Mac OS X, and Mac OS X Server, as demonstrated by how apple does Lion Server.
Download and install Lion
Download and install Lion Server Apps
So in this case and as always with OS X server Apple just adds some more Applications that the client version lacks. Additionally, Carbon Copy Cloner support discussion confirms it works with Server.