One unusual thing we do with our Exchange setup is we run a 365 day deleted item retention time. This is because we are a Performing Arts Hall and our business is molded around a performance season, which is around a year.
Our Exchange system is NOT large though, not by the standards you stated above, but one thing I can say is that about how the deleted items affect the store size. When we migrated from E2000 to E2003 we moved the mailboxes from one server to another new server. Before moving the mailboxes my Information Store was pushing 16GB (I also upgraded to Enterprise...) but AFTER moving the mailboxes, the Information Store was just 4GB! Since deleted items do not migrate, I had almost 12GB of deleted items! Crazy huh?