There are two reasons Admin Tools will block an IP address and not report anything in the Security Exceptions Log: IP blacklist or geographic IP blocking.
Are you using any Geographic IP restrictions? The MaxMind Country Database Lite used by Admin Tools to convert IP addresses to geographic information only claims 95% accuracy. This means that one in twenty users will have their country reported wrong based on the IP address. It's possible that your user belongs to one of the IP ranges that MaxMind's database misidentifies.
If you are not using geographic IP blocking at all you need to check your IP blacklist. Did you add your users' IP or their entire IP range there?
Finally, I'd like to note that the Unblock an IP feature always returns a success message. We just run a bunch of delete commands based on the IP you gave us. If the database does not report an error we consider it a success. The database does NOT report an error if no database record matched the delete request.
So, based on what you described I think that the problem is the accuracy of the third party GeoIP database.
Nicholas K. Dionysopoulos
Lead Developer and Director
🇬🇷Greek: native 🇬🇧English: excellent 🇫🇷French: basic • 🕐 My time zone is Europe / Athens
Please keep in mind my timezone and cultural differences when reading my replies. Thank you!