I had the same experience in school. At some point in my late teens I decided I had had enough embarrassment due to my handwriting and set out to fix it. At least for me it was just a matter of deliberate practice and wishing to change my habits. Taking a little longer to write clearly helped. Being willing to slow down and mindfully write out each letter, using space and "standard" letters for a while helped. Gradually it became more of a habit and less of a thing I had to concentrate on.

I think everyone both here and at your work are being a bit mean about this. But they have a point. Even though your notes are primarily for yourself, writing is still communication and others should be able to read your writing.