I think splitting the job would be best but what would be the best way to do this so I can get them to tape etc without conflicts? Can I do multiple backups from the same snapshots?
Each job will create its own helper snapshot. So even if you start multiple jobs at the same time, there will be some difference in time when the helper snapshots will be taken.
However, since the datastores are independent on each other (spread among different divisions), this second-worth difference should not matter that much.