My company already has a "local" backup strategy, but is willing to also backup data on our remote dedicated server as an additional "plus".
Some info:
Which software (both client and server side) you advice us to take?
I'm having good luck with a Barracuda Backup appliance. Its not cheap (a few thousand at the beginning and a monthly cost for off-site storage), but it gives you a simple to use tool with lots of technical support. It will also send the data off-site. The least troublesome product that I've used so far. By comparison, I've directly been involved with Retrospect (versions 4 through 6), Time Navigator, NetVault, and Barracuda Backup Service. I've been indirectly involved with the built-in backup in Windows, Veritas, and Backup Exec. On Unix and Mac, I've used rsync (command line) and a few Mac-only products.
Not sure if you have the budget or space for it, but thought I'd suggest it.
What are you currently doing for backup? If you have archives or files stored in a dedicated appliance or NAS/SAN device, I would look for a way to script copying the compressed data to another server remotely. That way you can schedule the transfers for off-peak times.
The best way to save data off-site is to save data to DVD/tapes and have someone routinely take them offsite in rotation (encrypted, of course). You don't really need data moved live to another running machine in most cases, unless you're a really big company that needs geographically spread data centers and redundancy. Never underestimate the bandwidth of a minivan full of backup tapes.
You could try looking at something like DFS or some other mirroring over IP solution. Again, don't know what you're using, but if you are saving data to hard disk images this could mirror data to another location seamlessly.
Solutions in a question like this depends on your situation. You need to define what kind of backup you're looking to keep...are you archiving data offsite? You want to have up-to-date snapshots locally and remotely instead of just older archives at the offsite location? Bandwidth available? How much data are we talking about in your backup? What are you currently doing to back up data? Are you storing just data, data+system state, or some mix of it (like system state and data locally but just data remotely)?
I'd still personally look at taking drives/tapes/DVD's offsite in rotation for safety as a viable option, but one note you have about encryption in transfer and storage...are you already encrypting the backup images? In that case you couldn't really necessarily need to encrypt the transfer of the data.
Assuming that you don't have file lock issue (open files, Exchange, MS SQL, etc), I'd recommend rsync. You can just write a simple batch file and schedule it to run using Windows Scheduler (the "at" command). If you're looking for something that has a few more features (and can handle Exchange), take a look at Backula.
I'm sure other backup software can do similar things but since you're in a Microsoft environment, Microsoft's own Data Protection Manager has a mechanism built in to do just this. You can do whatever backups locally and then have a remote box that connects to the primary DPM server and you pick which backups to replicate to the remote machine. You can even throttle the bandwidth it uses if necessary. This is more of a server/server solution but it works and supports encryption. Personally, I can't imagine using it in an environment with what sounds like just one box but your requirements are kind of backing you into a corner.
