I don't think it's an easy problem to solve.. my Palm T3 has the D-pad at the bottom, so it doesn't matter which hand holds the stylus (I think there's actually a leftie software setting too somewhere, to accomodate other things).

The N800 seems to be designed specifically for right-hand users, although most people aren't really right- or left-handed, they just have a right- or left-preference. I've met only two people in my life that were clearly right handed, their left arm was just an appendage - useless for everything.

But in this case the stylus is the problem - the writing hand is almost always a one-hand specific thing (well, at least if you prefer the hand-writing option.. with the on-screen keyboard you can probably learn to use the other hand, unless you're one of those few single-handed people). So, for lefties the N810 might be a better choice, as the thumb keyboard is always available and the stylus could be left alone (if you can stomach a thumb keyboard to start with.)

(If the N800 display could be turned 180 degrees upside down you could turn the N800, that would work except if you also wanted to use the kickstand).