Being restless I dusted off an EPROM programmer (MCUmall GQ-4X) I had to discover it does AVR ISP. The GQ software does not list the Mega2560 as a supported device so I tried the Mega128 and dumped the contents. I found the bootloader twice in the dump at two different addresses (0000 E000 and 0002 E000) - nether of them at the end of the address space.
I also found that the programmer is USB native (I think this was one of the reasons I bought it), it does not install a com port and avrdude could not find it. So I was stuck with the GQ software. I tried modifying the "device.txt" and copied and modified the entry for the Mega128, I renamed it and increased the code size to 262144 and added a device ID. Reading contents seemed fine and there was no sign of the bootloader in the correct address (should be 0003 E000?). Feeling confident I loaded the "stk500boot_v2_mega2560.hex" and hit the write button not really knowing the fuse state. The write worked and the "Verify Failed, Address=0x01E000, Device=0x0D, Buffer=0xFF". I'd assumed it didn't work again.
Upon disconnecting the programmer I discovered the L pin 13 LED started to blink. Had I breath life back into this thing? Or was there a different problem like a hardware fault or the bootloader looping? Anyway it seemed like progress. I plugged the Mega 2560 in via USB and attempted to upload a sketch. It worked! I reconnected my LCD module and tried another sketch it worked without fault. I'm very happy. 
So the moral of the story is:
- Don't assume just because it's easy to pick in the IDE menu that it won't render your Arduino board difficult to recover (or impossible without a different programmer)
- Don't assume that $2 eBay/Deal Extreme/GoodLuckBuy programmer can restore your bootloader especially on boards with larger flash memory
- If you cheap out on a programmer you might spend hours trying to work out what's going on- buy a decent one
- Assume any programmer can erase your bootloader regardless of the limited size it can read/write
- AVRdude does not seem to tell you what your ISP can and cannot do- dumping first might give you some idea
- Failing verification does not mean it didn't work, disconnect programmers and test boards
Things I still don't fully understand:
- Why does it appear the bootloader is in more than one memory location?
- Why didn't something stop me or warn me a little better about irrecoverably wiping bootloader (at least with the USBasp I have)?
- A check of the programmers capabilities and it's appropriateness to the board you're trying to program might have prevented a clown like me doing this
Thank you Nick for all of your time and effort. I owe you one. 