I have found this to be true with problem solving too. There are some complex programming concepts that are easier for me to work out on paper in cut down pseudo-code and then implement, rather then write out on the computer in comments and implement around. I think writing does use some other part of the brain.
I do a lot of thinking on paper, too. Although I never took straight notes in class (mainly because I didn't need to study), I would listen to the lectures, and when a concept intrigued me, I would start writing out thoughts about the lecture topic. I rarely looked back at those notes when finals came around, but the act of taking in aural information, processing it, iterating on it, and drawing out conclusions on paper, did a lot more than just copying the professor's words verbatim ever could.
I used to do a lot of free writing before (though I rarely have free time these days). I would choose a topic or subject, and just start writing, continuously. Whatever thoughts entered my mind were immediately transferred to paper, with no editing or selection. I would keep doing that until either I reached the end of the thought-stream (i.e., my pen stopped moving), or my hand cramped up. With practice, it was often the latter. It's a great tool for creativity, information processing, and overcoming the hesitation a lot of people feel when starting a work, whether written or otherwise. I highly recommend the practice.
Because I've gotten into the habit of thinking on paper, whenever I'm trying to work out a solution to a particularly complex programming problem (or any kind of problem, really), I start sketching things out either on paper or a whiteboard, sometimes in words, sometimes in diagrams. I start with an idea, and the act of translating that idea onto paper causes me to consider specifics. The idea may or may not change drastically before I'm through, due to concepts and issues that were previously unseen. Not only does writing this sort of thing down help me actually process and refine the ideas, but it also provides a thought record. I can go backwards through the notes to see how and why I arrived at a particular conclusion, which is sometimes useful months down the line.
I always carry a notebook and pen with me. I keep a small pocket sized one on me, and a larger one (with half graph paper, half lined) in my laptop bag. One can never be sure when inspiration strikes. A colleague once started writing on a napkin at a restaurant; I just looked at him with pity and silently handed him my pocket notepad.