Then there must be something wrong. I use Verbatim CD-RW discs and erased them over a hundred times without any problems. The number 1000 is not a marketing trick but a specification bound by the technology used to rewrite a cd-rw and written down in the Orange Book standard. Therefore, Orange Book compliant media is required to be erased and rewritten a 1000 times.
For more information check: http://www.components.philips.com/Assets/Downloadablefile/CD-RW+how+it+works_s-757.pdf
The "big" difference between CD-R and -RW is the dye. As the other layers mainly consist of the same material, rewritable discs use a phase-change recording layer. This chemical compound is sensitive to temperatures. CD-RW capable drives therefore must use different power calibrations of the laser to alter the state of the dye to write data to it. Optically, CD-R and -RW discs are technically comparable in quality but you also can buy rewritable media of low quality as you can with write once media.