I thought initially that DVD+MRW was a good idea (it's usually written that way, as it seems that it's currently supported on DVD+RW media and not DVD-RW media). However, in truth, it doesn't seem to have much to offer as things stand, not least because you need special software to read Mt Rainier discs in a non-Mt Rainier drive.
As others have said, if full rewriteability is your aim, DVD-RAM is probably where you should be looking. Unfortunately, at the moment, DVD-RAM speeds are still quite low and most of the popular and best regarded writers don't support DVD-RAM. DVD-RAM media is also relatively expensive.
DVD+RW (though not DVD-RW), even in the absence of Mount Rainier, can usually be background formatted - certainly that's the case for DVD+RW media in my NEC ND-2500A when using InCD 188.8.131.52. I'm fully aware of the limitations of packet writing software like InCD - I only use it to allow me to use Backup Exec 9.1 for Windows Servers with DVD, and even then do not use DVD for my primary backup media (I've got a DDS-4 tape drive).
There's no Windows OS support for Mt Rainier anyway - it's one of the things promised for Longhorn, which is unlikely to be with us for at least another year. Until then, you still have to use packet writing software, even with a Mt Rainier drive - and that packet writing software will handle the error correction. I'm afraid I'm not aware of what support there is for DVD-RAM, Mt Rainier and 'ordinary' DVD+RW (that is DVD+RW without Mt Rainier support) in Linux - my UNIX usage is all on FreeBSD and currently all on machines I don't sysadmin myself.
The limitation on the number of rewrites possible is a limitation of the phase change layer used in the media, and may not be easily overcome. I'm not fully up on the technicalities of DVD media, but wouldn't be surprised if it's a trade-off - you can't get the rather greater number of rewrites possible on DVD-RAM without sacrificing compatibility (as DVD-RAM does over DVD-RW and DVD+RW).
If you're anticipating a replacement of your tape drive any time soon, I suspect that you have a relatively small tape unit. There'll have to be affordable blue laser rewritable hardware and media before my DDS-4 unit is eclipsed.
I would have liked DVD+MRW and DVD-RAM support - but the marketplace doesn't seem to demand them, and they're not available on the current market leader drives.