I've delt with a couple clients who have had 600GB and just under 1TB of mail storage. What I recommend is either Veritas Backup Exec/NetBackup for Windows systems or AMANDA for Unix systems. Both will deal pretty well with extremely large amounts of data. As for the tape system itself, I personally prefer to stick with DLT tapes, even though LTO and AIT are a bit better. I've just had next to no problems with DLT tapes and out of the probably two thousand DLT tapes I've used I've only had maybe 50 go bad on me. If you want to go with something a bit more up to date, can't go wrong with anything from Exabyte or HP. Media, Sony or Verbatim.
The big thing I will warn you about is time. It takes pretty much forever to backup that much data, on the order of days. You'll see one backup finish just as another one is ready to start, so let your client know it'll take some time to backup that much info. And if you are backing up over a network, make sure it's a dedicated backup network. I can't stress that enough. I've delt with idiot companies didn't want to install a second NIC card on their servers to backup over and wondered why their network performance was so damned slow during backups.