There were clay and wax tablets that could be erased and re-used (unless, for the clay tablets, you baked them, in which case the writing became permanent). I don't know if they were still in use during the Middle Ages.
Thank you for the info, it's nice to read about a rational and balanced view for a change
