The resolution for this was to login as the user via Outlook Web Access and disable it in there. To do this, log into OWA and go to Options > Block or Allow Settings and choose to turn it off – then save the settings.
There is a powershell cmdlet to disable this for Exchange 2010, Exchange 2013 and Office 365. The Cmdlet is
You can find more info here: http://technet.microsoft.com/en-GB/library/dd979780(v=exchg.150).aspx