As an interviewer, I'd much rather see your intermediate steps - the messy parts, etc. I feel like I can get a better idea about how you work and think. Interview questions (for me) aren't about "can you solve this" they're more about trying to see how you work. I ask questions about decisions you made, and I like it if you can talk about what you're thinking.

Interview problems are contrived. I don't care if you stumble a little bit. Heck, I'm always happy when I see someone start off the wrong way, notice that something's wrong, take a step back and go a better path.

If you go off with a paper and pen and just give me an answer, I miss out on a lot of that. And even though the anxiety might not show how you normally interact (and I totally understand that) - I can't possibly get any sense as to how you work in a collaborative environment.

I've never had anyone ask to do problems on paper instead of a whiteboard, and I wouldn't refuse it to them - but I just get a feeling that I'd be less likely to be inclined to hiring them - not because of the paper, but because there's no way to see the things that I most like to see.