Both banning by IP and cookie are, as you say ineffective.
If you need to block specific users then you're only recourse is to require all users to authenticate using an email address - they don't need to supply a password - just generate a random hash and store it against the email address in a database table, then send out a clickable URL with the hash in the query. Then, when the URL is accessed, drop a cookie with the hash in it (and an expiry date long in the future).
Then whenever a user access the site, check the cookie against the database to see if it belongs to a banned email address.
The downside to this is that it shifts the burden to the legitimate user. E.g. if they registered from a domestic ISP account using the ISPs email service, then they won't easily be able to access the site from an internet cafe.
And of course, its relatively easy to get a free email address.
C.