You did not mention whether or not you are using the same name server internally as we see externally. I queried the name servers ns1 and ns2.parle.biz, and got:
Addresses:22.214.171.124, 126.96.36.199, 188.8.131.52
This leads me to suspect that you may have an internal name server referencing the same domain, but a different set of data files.
Try doing the lookup/telnet/whatever by hostname terminated by a period – so that it looks like “mail.parle.biz.”
Also, when you open nslookup at the command prompt, check the SOA value for parle.biz internally, and see what it says about it.
> set type=soa
And let us know what results you get.