I agree that removing the reorganise button is a bad idea. Remember - we're building this for our content authors, not for ourselves! :-)
Regarding Tim's suggestions
(1) and (2) are interesting, it would seem the way to do this would be that you click "reorganise", and this displays "save" and "cancel" buttons that would actually send the reorganisation to the database, or revert it respectively. I don't know how high a priority this is.
(3) is a bit strange inasmuch as it's a totally different publication process from other publication the site. Perhaps a better solution is to make it easier to publish the entire site, or sections of the site? The real problem here, IMO, is that the current publication tool is a bit crap.
(4) would aid reorganisation; however, sometimes it can get weird if an entire UI-element such as the tree jumps around on screen - you wind up losing the page that you were going to reorganise. Perhaps you could do something kind of like the OSX dock, where a bigger amount of space appears when you drag a particular page around.