After a few weeks of this, my handwriting got back to a decent quality and efficiency and now I find that I take notes on paper for all sorts of things. It's great for working through problems.
I tried a whiteboard for a while and it just didn't do it for me. I think there's something about the tactile experience of holding a notebook in my hand and scrawling on it with a pen; the movement, the sound, the texture of pen on paper, not to mention being able to keep and flip through previous work and go back and make notes in the margins that makes it far better than trying to work out problems on a computer or a whiteboard.