dilberts_left_nut:
This is caused by that server treating 'lincolnshire.gov.uk' as a non-local domain even though it is listed in the MX records for that domain.
In other words their setup is borked. 
It has nothing to do with where you tried to connect beforehand.
Thanks. I understand in principle what you are saying.
So, is the server that is handling the request misconfigured? Or, is the SMTP server in the wrong domain/sub-domain within their forest (assuming they use WS2k3 AD)? Or can it be caused by misconfiguration of software?
I'm wondering how this could be done. If I was to try to generate the same error message from our copy of Mercury32 so that anyone trying to send mail to our domains got a 550 Relaying Denied response, how would I achieve it?
I'm still learning about this so if anyone would like to help out by explaining this I'd appreciate it. I've worked my way through the first part of RFC 2821 and now understand most of the elementary commands used by senders/receivers, but the finer points are still a black art :)
Cheers!