There are some good discussions on backup already on Server Fault. I'd have a look at them:
I notice that you're already ruling out tape. I'd do a cost-benefit analysis of the alternatives pitted against tape before dismissing tape out of hand. It sounds to me like you've either got a bum SCSI controller, cable, or bum tape drive and it's unfortunate that it has soured you on tape because tape can be very reliable and robust.
I did some calculations a few months ago (posted on Server Fault in one of the questions above, but not updated) and found that tape wasn't necessarily the most expensive route. Call me a traditionalist, but tape has worked very well for me and my Customers, and has proven to be reliable and suitable for disaster recovery. I tend to think that a lot of the "horror stories" associated with tape being unreliable often stem from backup strategies that don't involve testing of the backups after-the-fact. As is often said, backup isn't about backup-- it's about being able to restore.
Having a maintenance agreement for your hardware is, obviously, a component of any robust solution as well. You state that you need a backup you can restore to other hardware, but I'd caution you that your SBS server's "System State" backups aren't restorable by any Microsoft-supported means to alternative hardware. Hopefully your other server is a domain controller, since you'll be losing Active Directory (and, thus, making your Exchange data fairly difficult to get at) if you lose that SBS Server computer.
Having a maintenance agreement on the tape drive and / or server would get you out of the mess that you're in, in this case. It's particularly critical since you've currently got a backup, assuming you don't have another domain controller, for which you really need the identical server hardware available for restore.
You shouldn't center your whole backup regime around writing backups to an on-site storage device. Backup is off-site and offline. Anything less isn't backup.
I'd question if you can restore fast enough to get back up and running in a timely fashion if your main backup is an off-site device and accessible only through your Internet connection. If your renmote backup provider has a provision to ship you a physical storage device I could see that working. If you have to download your entire backup corpus over a consumer Internet connection, though, I'd think that you'd be talking about at least a couple of days to get everything back up and running. Ouch!
Avoid SATA tape drives - the only one's I know of take DAT/DDS tapes (which is a horrible format).
I'd suggest a SAS or SCSI LTO3/LTO4 drive. LTO is effectively the standard tape format.
Best Answer
Shoe-shining refers to the tape drive stopping and rewinding due to an empty data buffer or inconsistent incoming data stream. This was a problem with older DLT drives. LTO drives shouldn't experience shoeshining. The LTO format/standard was partially designed to eliminate this behavior. HP drives, in particular, have a variable write speed to help reduce this effect. The Ultrium 960 should shift down to 27Mb/s as a minimum streaming speed.
We're missing some of the information that could be helpful in diagnosing the issue...
Tell us about your actual hardware setup. Looking at a local HP Ultrium 960 drive, I'm getting write speeds of ~2,000 Megabytes/minute (33Mb/s) across a mixed data set (with hardware compression ON). This is with an HP ProLiant DL380 G6 server and an HP-branded LSI Ultra 320 SCSI HBA.