I notice Doug's PSK's (saw some at a camping store) now come with normal golf pencils.
If you want an ultra-tiny writing implement, you could use a piece of the lead from a drafting pencil. You can get those leads at art stores. They're a little smaller in diameter than those toothpick pencils, i.e. still thick enough to write with if you're a little careful. I think 2mm thickness is standard.
(Edit:) Googling found this:
http://www.pencilpages.com - wow. More pencil info than you could want, and a classified ads section where you could ask about particular types of pencils.