I remember this being a common problem back when 800k disks were popular. We concluded that sometimes some critical piece of data on the disk gets corrupted and Macs refuse to touch the disk afterwards.

The solutions we used with great success were to either:

a) hit the disk with a bulk tape eraser, then re-format OR

B) format the disk in a 720k IBM floppy drive, then reformat in a Mac

Either solution "fixed" the disk properly and it would then go on to perform faultlessly.

Never thought of using Disk First Aid though: that's a good tip, especially when you don't have either of the other options available - thank you.