Stuck with draconian security restrictions after adding and removing corporate e-mail account
My response is specifically in respect to Exchange based device administrators.

What you should find is, dependant on some security policies device administrators cannot be removed without a device wipe. This is to protect company data and is set at the exchange level and conformance is met by Android.

I have followed the process on android 4.2.2 and it works however, dependant on which company exchange account I use (i work as a sysadmin contracted to many companies managing many exchange servers so different policies) i can see different behaviours. 

If you have not been asked to wipe your phone when device administrators were removed, then I'm shocked. I've not seen this behaviour on any exchange server I've tested with. 

I'm sorry to say that generally once you admit an exchange administrator you are stuck with a factory reset.

That does not mean all YOUR data is lost though. You may do a SMS backup, Application backup and if you have root and recovery, a system backup. Do these to your internal SD or external SD as these will not be wiped in a factory reset. If you are concerned about encryption depending on which file systems you encrypted (usually it's just system, not internal or external SD cards) you may want to copy these backups to another device.

Now do your wipe.

Restore your backups and find your applications, sms's and all your photo's etc should be exactly as they were. All that will be missing is the exchange accounts. 

This is tedious I'm aware. However this is becoming more common in a BYO device oriented corporate world.