That happened to me and I was royally pissed, until I realised I had to put my own Spys in the City to eject him. Once that happened a few times I realised I then needed an assassin to kill the little bugger so he just didn't walk straight back in.

He was a Briton Spy and he was damn good. Sometimes the AI is very good like that.