Without any knowledge of your server specs, I'll just point out some tips for making the job smaller at least so it won't take so long.
1) Use Single Instance Storage - This makes one copy of any attachment, regardless how many people received it. If you are talking large attachments like images, or mp3 songs sent to 20+ people each message, it adds up to a significant amount of data being backed up for each message. SIS cuts that down significantly.
2) Use Global Excludes - If you globally exclude certain folders like "Deleted Items" or "Sent Items" you will save a huge amount of space and time. Global Excludes are done by selecting the MS Mailbox item, then right clicking on it and selecting Advanced File Selections. From there, enter "**\Deleted Items" (minus the qoutes) in the path field and select Exclude on the right side of the screen (defaults to Include). The double asterik will find the Deleted Items folder anywhere withing the users mailbox structure and not back it up.
3) Make use of Full\Differential\Incremental backups - Many users simply do a Full backup everytime, which is a complete waste of time and storage space. Do one Full backup a week, with an Incremental and a few Differentials in there. So for a Sunday-Saturday week, you may do a rotation like F/D/D/I/D/D/D or a similar rotation that works around your schedule.
Always set the jobs to run at night to avoid the high use times at work. As for your server, perhaps it is simply toi slow or not up to standards.