I did my little test with maybe 20 minutes of usage before I charged.
As for initial handling of battery I discharged it to 25% the first time, and after that I just kept charging when it reached 50% (or earlier) except for once or twice when it as at 25% or less.

But I know from my Palm T3 that the charger circuit in the unit could get confused (particulary when new or with new battery), and you had to do something called an "in-cradle reset", which was to reset the device while it was attached to the charger. There is no notion in the N800 docu (thin as it is) about anything similar, although the symptoms you describe could sound like it needed one.