AMANDA will probably be your best bet. Use it to backup the Unix servers, and use Windows own built in backup program (dumbed down version of Veritas Backup Exec) to backup the Windows' boxes to file. Use a Samba share from the Windows boxes to backup to the Linux box.
Anant Systems/i|o Server
If it's a dedicated server you should have root access to it. If you don't (like how Verio does the root2 accounts) then you still have root level access. If that doesn't allow you to do it, set it up for everything and just have the hosting company finish it up for you.