Backup problems

We just added another Domino server to the mix and the additional 40 GB of data broke the back of our Tape backup scheme.  We were running a standard GFS backup scheme but with the amount of data now required daily it just became to overwhelming.  I'm going to have to look into either a new tape drive with multiple heads or change the scheme altogether.  Our Irvine office has an identical setup (tape drive & servers) and my boss suggested splitting the jobs over two locations.  My only problem with this is then our offsite storage will be split into two places.  I suggested implementing transaction logging, so I wouldn't have to backup the entire database every night but that was shot down for multiple reasons.  I'm not sure where I'm going to go with this.
-PC