Sounds like you have checked everything out. I had an Oregon 400t (same series as your 300) but gave it to a friend many years ago. It was a great unit in its day, but the screen was just terrible and processor really slow.
Only other thing that occurs to me is whether you have used it with a Macintosh, because that will create invisible files that can fill the memory. I'm assuming that isn't the case, since you are seeing so much free space. I also wonder exactly what "memory" means in that error message. Could it be a problem with the device's RAM instead of flash memory? Or perhaps the NVRAM that isn't user-accessible and holds the system firmware?
The segment limit could be a problem, IIRC that device has a limit of 4000 map tiles total (including internal memory and card). If you have removed all the maps, I don't see how that could be an issue however.
I'd say it's time to give it a decent burial and move on.