Alright... Ill see if I can take a shot at this:
In your screeny you just posted it looks like you dropped your dotclock by about half and interlaced, which is probably why you are getting so much more luck...
To use the XFree86 Modeline Generator, I first enter some ballparks for the monitor at the top... These are just outside limits you want to keep the view inbetween... I put in 15.6 to 15.9Khz and 43 to 63Hz... I leave the dot clock frequency blank... I don't know what the max bandwidth of an arcade monitor is, but I don't think its very important for this.
After that, I need to fill in visible region, refresh rate, and check interlace if its required.
Lets enter 640x480. i aim for 63Hz. it gives me a dotclock of 25.5 and tells me that my horizontal refresh rate is way to high. I check "interlace", and press okay again.
little closer, 16.02... if i try to get a little closer by lowering the refresh to 62... bingo, I get a horizontal refresh of 15.75, and a modeline of...:
Modeline "640x480@62i" 11.72 640 672 712 744 480 491 494 505 interlace
Not in the proper format, but it should suffice... However, I found a better way to produce modelines that worked for my methods... here is the spreadsheet that i use:
http://www.asuaf.org/~dboyer/avga_w_linux/modelinecalc.xlsBold numbers are for changing, italics are for modelines (output) you enter your visable range, and then play with the dotclock to get a desirable range... on the left is advancemame recommended values, on the right is the better value for me... Doesn't do interlaced, however... I'm about to go back for my trip back to Uni in a couple minutes, so I'll have to get back to you in a couple days if you need more assistance... (however, no more mame machine :-()
BTW, a 800x600 might look something like:
Modeline "800x600@50i" 14.50 800 832 880 912 600 614 617 631 interlace