We don't mean to sound patronising but from a distance it's sometimes hard to diagnose faults like this.
Our first guess is the burner as you stated that all programs were having trouble with a full erase, you also mentioned that a quick erase works but a full erase doesn't. If the same command fails from all your burning programs I can see why the drive was suggested as being at fault. My guess was the RW itself if you believe the burner to be ok, this is because they are not always very reliable when compared to the Verbatim DVD