Hey Jon,
I'm gonna' rag on the belt sander...It's really easy to gouge the surface, especially with the tougher grits and softer woods, and you have to be supremely careful about creating waves/uneven ripples across the entire surface. Granted, it doesn't leave the squiggles that a small orbital can, but I am a huge fan of 6-8" random orbitals. They can take down a lot more in a sitting and can be more forgiving, especially when you're bringing two sections together.
As for the old varnish spots, if the new finish is darker, then you just need to scuff them so the new will stick (as long as there's not a substantial build-up that will cause lumps). For paint spots you're better off getting it all out though, as it will show through. Most people take it easy on corners because it's so easy to put something there when you're done, like a plant, small child, etc. If you're having a really hard time in a corner, a Japanese scraper is a great tool, and beats the hell out of a Mickey Mouse corner sander (which is really only made to make your wife think you're busy)...
Good luck!