I recently purchased a N95 and discovered that its headset/microphone unit works great with the N800. This is a much better headset/mic than the cheap one included with the N800 by default. The microphone produces much better sound than the default N800 in my limited testing with Gizmo and a few guinea pigs. One of the things that I really like about the N95 headset is you can use their default included earbuds or plug in any standard headset into the microphone portion of the unit. I am not sure how available these are when not purchased with a N95, but you might be able to order them from Nokia as a replacement part.

I'm using the v-moda vibe duo that is designed for the iPhone:

http://www.v-moda.com/collection/mod...ibe%20duo.aspx

It works perfectly with the N800 and with my iPhone, but I have to insert the plug about 1mm short of all the way to get to work on the Nokia. The two devices both have a 3.5mm three-ring headphone jack, but apparently there is a very slight difference.

The sound is awesome, the fit and comfort are great, and the handsfree function works great for me in Skype. Much better quality than the cheapos that Nokia provided in the box.

Now if Nokia could just add A2DP and the handsfree profile, we'd be all set...but that's another can of worms I don't need to open again...

I just got a stereo headset from Rivet ($19.99 from Amazon) and it's pretty good. One feature with this one and with the Apple iPhone headset is that you have to keep the microphone button pressed down all the time while on a call. Otherwise you get crappy earbud sound, and no mic sound at all. It took me a while to work that out

I don't like using a speakerphone but actually the N800 works pretty well if you just hold it next to your face like a regular smartphone.