It's an interesting phenomena, but since the price of CDRs has plummeted it has become tougher to find good CD-RWs!
Today I checked a few places only to discover that most of the mass-market stores are going for the cheapest bulk packs they can find. MP3Mogul's comment about the high-speed Memorex CD-RWs got me thinking, my Best Buy was out of them, but a nearby Office Depot had some of the new Maxell high-speeds and they had "Made in Singapore" on the package. So I played the hunch and sure enough, acccording to CD-Indentifier, they are made by Misubishi Chemical.
So tonight I change the bitrates on the videos to fit on 74 min instead of 80 and I should be all set.
A non-trivial undertaking!