I made a series of PNG files in paint, all of them at 584x754. I played around with some lines until I found where they got cut off. I then made two more pictures, to double check: One with a single pixel border that should be just visible, and one with a two pixel zig/zag border, with one pixel visible and one not. They appeared exactly as I thought they should. If this is a valid test, then the actual usable screen size is 540x718. It looks like my original guess of 36 pixels on the bottom was right! I didn't notice the 44 pixels off the sides, though...
Anyways, if anyone's interested in the epub I'll upload it somewhere. I'm looking forward to testing it after the changes are out. Kovid, if you'd like me to test it before you update the actual program, I'd be more than happy to. Just let me know how.