Based on my conversations with Nokia, you cannot buy replacement styli for the N800 in the US and if your screen is damaged by a third party stylus, the warranty is voided. Quite a Catch 22.

As I have missplaced one of my N800 styli once (but later found it), I am hesitant to use it regularly. As a result of some research, I have been using third-party Pentopia series styli from Pilot. They seem to very well made and very gentle on screens.

My favorite so far is the Pilot T10MG Compact Tetherable Stylus. They are very affordable and compact and I have been buying them from http://www.stylisource.com.

I'm not sure if anybody else was looking for a good substitute, but I recommend them.