This probably isn't worth much, but I've had good results with a Lenmar replacement battery in my N810. It doesn't have the capacity of the "equivalent" Nokia battery (BP-4L), if the Nokia battery is genuine and brand new. But it's much better than a counterfeit, worn out or expired Nokia battery.

I don't know the status of the battery for the N800 (mine's still functioning), but if it's less popular or no longer used much, it may be that the "new" batteries you're finding are counterfeits or questionable refurbs.

The Lenmar batteries are readily available (I think mine came from Office Max) and reasonably priced, although I see some allegedly genuine Nokia batteries that are cheaper.