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!
First try replacing your cleaning tape (order a couple).
The "50 cleanings" figure for a cleaning tape is kind of like "every 10000 miles" for oil changes in a car: Under ideal conditions that's fine, but it's not a guarantee of performance. If you're using the cleaning tape on grungy old heads in a beat-up drive it won't last anywhere near that long: I've seen cleaning tapes come out brown after ONE cleaning cycle, and I certainly wouldn't reuse them for 49 more.
Your tape may look clean, but hold it up next to a shiny new tape and you may notice a surprising difference.
Also note that the "CLEAN ME" message going away just indicates that a cleaning cycle was done -- The fact that the cleaning message (and presumably the media errors) come back after "a few days" instead of months makes me suspect that your cleaning tape isn't doing the job (the drive is picking up errors, which triggers it to demand another cleaning).
If running a fresh cleaning tape and using new tapes for the backup doesn't make the problem go away you may need to have the drive serviced/replaced.
I don't think your network errors are related - a media error is typically thrown by the tape drive, and would be independent of any network problems. You may want to open a separate question about those errors (please be as specific as possible if you do: "network error" is one of those meaningless phrases that can be anything from "I couldn't open a connection to the backup client" to "I'm using ISCSI to talk to the tape drive and it ain't working!")
Best Answer
You could try out some older Linux distributions. The last Linux kernel that included the 'ftape' module (QIC80 support) was 2.6.19.
The ftape module
ftape patch for more recent kernels
Cheers