Exchange Backups

We are running Exchange 5.5 on Windows NT 4.0. We are backing up this server using Veritas Backup Exec but we did not realize that it was not backing up the Exchange databases until we needed to restore a mailbox and could not. We are using an older version of Veritas and can not just buy the Exchange agent. We have to upgrade the backup software and then buy the Exchange agent and it is over $1000. We can’t spend that much right now but also need to backup our email. I think we can stop the Exchange service and get a backup that way but that is not a very good option and I am not completely sure that this will work. Does anybody know of other backup software that is less expensive and reliable or any other options that will work? Thanks.