I used to have this problem with some brands of pre-formatted disks (PC format).
My solution was to use a bulk eraser that was originally used for reel-to-reel and cassette tapes. The one I had was Realistic brand (Radio Shack). I could always format after using that.
(I recall also that some viruses would cause similar symptoms but you then also wouldn't be able to format 880K disks.)
