Sorry for the late reply; forums have been taking a back seat to our huge helpdesk ticket volume, unfortunately.
The message is intentionally vague to avoid giving an attacker information about exactly when he can resume a bruteforce attack. You can configure this feature in detail in the admin settings, including the number of login failures that trigger the lockout as well as the duration of the lockout in minutes.
There is no UI for removing bans because, unless you configure it otherwise, the bans are only 10 minutes in length. By the time a user could complain about being banned, he would already be un-banned.
Clearing the browser cache won't do a thing, unless the browser has (incorrectly) cached the page that displays the login failure message.
As for how it's tracked, yes, it's in the database and it's pretty straightforward. Check the login_bans table and just remove the row with the "ipaddress" column you want to un-ban.