I can tell you that I have restore 320GB in 36 hours.  This 320GB consisted
of 2+ million files that were spread across 17 tapes over a 6 month backup
span  and was performed while there were about 3000 users accessing the same
Win2k Cluster node.  I my opinion, even though it took 36 hours, this was
not a bad performance on the restore for a complete disaster recovery.  We
compared this to a server we had to restore under our previous backup
software and it would have taken about 3 weeks (GB for GB).  I have restore
other servers that are in the 40-60 GB range with many, many files and a
backup span of 2-3 weeks and the restore time was less that 3 hours.

The major thing you want to do is set your priorities on which restore need
to be completed first and set you users expectation to the correct
timeframe.  I though that would be hard to do with 45,000 employee's but it
is not really that bad when you take into consideration that most of you
restores will be from previous day and would be in DISKPOOL cache if you can
configure it correctly.  I have had a request to restore a directory that
contained 1000 files (about 20MB total) and it restored about 10 seconds
since it was still in cache.