The SEALS got their idea of carrying a pencil from the British SAS. That was always the strategy of the lads in the UK - because a pencil was a better all-weather writing tool. And let's face it, you can always sharpen a pencil.
A Fisher Space pen refill is smaller than a pencil, is more durable, lasts longer as pencils actually do run out (the main advantage is that you can see how much longer the pencil will last) and the Space pen refill works better in wet conditions. Just carry a fresh Space Pen Refill. I wrap duct tape around a Fisher Space pen refill to allow easier writing.
The INKA titanium pen is also very good and allows full size performance but it is ridiculously expensive.
For a full sized pen the Dealextreme Tactical pen is also a favorite.
http://www.dealextreme.com/p/cooyoo-tp3-military-survival-defensive-tactical-pen-48875