I am with DNSMadeEasy and they swore black and blue that the problem was not on their end. However, when I delved deeper into my DNS configuration I found 5 extra DNS servers assigned to my domain and one of DNSMadeEasy's domain servers has been redirected to this a-holes server.
I admit that I was using DME's default server names and some of it was my stupid fault anyway but am not too happy that it happened at all. If *think* I have cured the problem by assigning my own vanity servers to my domain plus creating a custom SOA record to define my parent server.
To say I am a little uneasy with DME is an understatement. Does anyone have a DNS supplier recommendation that isn't going to cost me the earth to move to?