There is no 100% solution to your problem.

A user can use a wide range of strategies to bypass any possible action: delete cookies, use a VPN, even change its device (mobile phone, pc, laptop). You mentioned them.

What are the options I have?

That said, IP adress and a browser fingerprint is your best bet. There are libraries for JAVA (and probably C#) that can extract a fingerprint from the HTTP Request. But again the user could just change his browser signature or switch to another device.

Therefore is might be helpful to change the idea behind it from “completely locking a user out” to “making it hard for a user to gain access.”

Edit:

“A device id” would basically be the MAC address, which can not be obtained via a HTTP request. So no, there is no device id you could use. A device fingerprint is the closest thing you can get.

An Idea:

You could use a mobile app to authenticate a user. An app could obtain a device id (MAC address or IMEI for Android). Use the device id from the phone to register a user. You’ll only need the mobile app for registration. If you ban a user, he won’t be able to register again using the same phone. (This is of course not 100% reliable, but more reliable than anything browser based)

The only fool proof way is to force users to identify themselves with an authentication mechanism.

Identification is the “Who are you?” question, and the answer can be a user name, real name, email address, browser finger print, etc.

Authentication is “Who are you and prove it!”. In computer security this is implemented by requiring the user to supply a minimum of two things, such as the user name and a MATCHING password which have been established in advance. In this regard “things” are grouped into one of three categories:

1. “Something you possess” (An object such as a One-time pad)
2. “Something you know” (such as a piece of secret information, typically a password), and
3. “Something you are” (presented as a digitally encoded representation of a piece of your body, eg a fingerprint scan)

Access control is always a trade-off between convenience and security. To make a system more secure you necessarily have to make it less convenient to use. The most convenient system is where anybody can just do anything without having to supply any credentials. Such systems are quite rare these days, but some public Wikis still allow anybody to edit the content. On the end of the spectrum high security systems, such as the ones controlling nuclear reactors, require you to be physically at the system console in a room where you must book your access in advance. Everything else falls in somewhere in between.

After Identity and Authentication comes the third concept: Authorization, which means “Is the identified user allowed to perform the requested operation”

Authorization is meaningless without an authenticated identity, because if you are trying to prevent misuse of a system without authenticating the users, then you simply can not be sure that users are who they claim to be.

So basically it amounts to you having to force your users to supply identity credentials, which can be set up through a registration process.

The question you must ask is how much do you care about preventing misuse of your system and how much inconvenience will your users be willing to put up with. People are quite used to having to log in to web based services, and often quite fed up with misuse such as spamming and cheating, so most people will accept that they must register to continue using your system.

Are we talking about cheating at online voting stations? Cheating about having received a soup kitchen meal ticket? An online board game? A (small) banking application? A school subject testing application? A Job interview screening test for a programmer position? These all have different requirements because the users are different people from different backgrounds and with different skills and resources.

Update:

Since you are already authenticating your users, one concept (that I am currently investigating for my own application) is using a 3rd-party to do the hard work in providing user identification and authentication. Basically for my application I will be using a form of OpenID. I will not be supporting local registrations, users will only be able to register using their Facebook/Google+/LinkedIn accounts. My objective is different though – I want to make it very easy for users to sign up. Your objective is to eliminate disposable accounts by making it harder for users to register disposable accounts.

This process alone will not make it impossible to set up disposable accounts. What I would suggest and what other web sites, including StackExchange, does to a greater-or-lesser degree: Combine the identification with a trust-score. Basically a new user should not immediately have the authority to post. They need to first earn trust by some means. SlashDot allows you to filter and by default filters out some low-score posts. Many sites require a new user to be vetted by an existing “resident”. Forums display a user’s registration date and number of posts as a measure of trust. Sites like SE also allows existing users to “vote” or “thank” users for their valuable and helpful posts.

The concept is to authorize the action of posting and/or rate posts.

Posts from users with a low trust score may need to first be scrutinized and “accepted” by a trusted user before it becomes visible to the public.

Update 2

Higher forms of security may require more than two of the three types of things a user must provide to authenticate themselves. A very common thing for people to “have” is a phone and you can check it by sending a text message with a unique code, which the user must enter back into the web site to prove that they have the phone with that number. Once they have entered the phone number, and you have checked that the number is not on a list of banned numbers, you can grant them a higher trust score.

With such a system you can change your existing system without inconveniencing your existing users too much. For example allow all users to register and log in. In order to post they must either get a high trust score or they must supply a phone number which you can verify. The phone number requirement does not completely make it impossible for people to misuse the system, but makes it rather difficult to create many disposable accounts.

Note that this system have some disadvantages. Services like Amazon SNS only sends text messages to American numbers. Messaging providers to other countries charge a fee to deliver the message, which could be a problem if your web service cannot afford the cost.

One other mechanism for identifying the user device exists but only if the user accesses the service through an application installed on a mobile device. An app can read the device identification number. This can also be used as a means of “trusting” a user because people only have so many physical devices, but web based apps does not support reading this type of information from the device.

Why don’t you use phone verification? A user can’t have ‘n’ no. of phones or at max of 2 or 3
When you ban a person, ban his phone no. too so that he can’t verify again.

Simply use on-call/text user a code on his phone to enter into the browser.
This will not only help you identify the genuine users also help you keep spammers away.

Maybe you can add some benefits for long-term user or disadvantages for new users like more strict rate limiting or CAPTCHA. You can also use a reputation system. One can create a new account if banned, but without all the advantages of long-term user.