Doing crosswords in pen has taught me that ball points can write very faintly if you use light pressure, so that a later overstrike visually dominates.
I found that doing easy and medium Sudoku in pen is remarkably enjoyable, far more so than it ever was when I would make temporary marks. It's harder, and I'm not very good at Sudoku in general, but it really reinforces the "you have to prove it ..." mindset. Strangely, even though I am slower, I seem to get stuck less often.
I've never programmed on paper to any real extent but doing crosswords in pen certainly made me better at crosswords.