Have you considered Mup? (http://www.arkkra.com/) It's commercial, but cheap, and you get the source (which you can compile and test before you buy). I'm not using it on the N800 yet, but I will. I've bought a license ($29 IIRC) and I use it on the PC.
It's _not_ a graphical notation application, it's a textual notation (easy enough to learn) and you can use any editor you want. It can create midi too, which is great for catching mistakes. I use timiditity together with Mup on the PC, elsewhere in your posting you indicated that timidity is available for the N800 so that's one problem out of the way for me at least. The notation output of Mup is Postscript, but Evince is supposed to support that.. I'll see soon enough when I just get Mup recompiled for the N800.