Instead of attempting to backup your regional servers via your internet pipe, you should look at backing up the “server” locally.
In your head office, I would setup a server for each region so an additional 8 servers in total of 14 servers in your head office. I would then install either XoSoft Replication or DoubleTake’s Replication where the Regional Server is the “master” and your HQ Regional Server is the “slave”.
Now install your backup agent on this “slave” server and you can back it up locally and much faster.
As per backup, you can use your existing or look at Backup Exec or Arcserve or Legato.