I have been having this issue since 1.6.9 and now on 1.6.10. If I ban a user permanently they stay in the ban list however after about 1 days time they can log in and use there accounts again. I have over 700+ bans in my ban list.
When they try to log into your forum (providing you have not changed the Banned group permissions) they will receive a none permission page telling them they are banned.
I had 2 perm banned users that were in the banned list that was supposed to not have access to anything indeed somehow able to start using their accounts again. The only thing I could think of doing was to find there account in the ban list and do edit and update to force the ban to take effect again. I found that really odd behavior and it happened in both 1.6.9 and 1.6.10. I am waiting to see if it happens again.
I've never noticed this, though I've never been banned. Will test it locally. Do you have any plugins installed that may affect the ban system?