How to store uniquely a GCM registration id into M

I'm setting up the server side of a Google Cloud Messaging mechanism, using MySQL to store the registration ids provided by the mobile app. Giving that Google can issue up to 4k registration ids, I'm forced to store them in a TEXT field. All good so far, the problem is that I have to handle situations like this:

A user logs into the app
The app requests a registration id from google
The app sends the new registration id to the app server
The server stores that registration id and links it to the user who's currently logged in
That user logs out and a new user logs in
The app sends to the server the same registration id as before
The server must be able to see that the registration id is already in the database but linked to another user
The server unlinks the registration id from the previous user and links it to the new logged in user

So the problem is that I have to ensure a uniqueness for the registration id in the database but I cannot add a UNIQUE index for that TEXT field.

Possible solutions that I could think of:

Compute a hash of the registration id and force that hash to be unique, but there could be collisions.
I could store the unique device id along with the registration id and enforce that device id to be unique. The problem I see is that I don't know how long can be an android device id, and I think that there are some cases where it isn't available.
I could perform a search every time that a new registration id is received, but I think this would end up in a very poor performance operation.

I'm sure that I'm not the only one facing that problem, but I can't find good solutions out there. Any thoughts on how can I solve this?

For storing the registration ID itself it's better to use VARBINARY(4096) column. It's more efficient than TEXT if you encode the registration ID with an efficient character set (such as UTF-8).
For efficient search, you should still have an additional indexed hash column (BINARY(32)) - we use the SHA-256 digest algorithm to get the 32-bytes hash from the registration ID. The hash column doesn't have to be unique. Collisions should be very rare, and even if they occur, your query will give you a small number of registration IDs which share the same hash, so it won't hurt performance to test in your Java code which one of them (if any) actually matches the registration ID you are looking for.
If you choose to store a unique device ID and search based on it, I suggest you assign your own identifier to each device. That identifier can be (for example) BIGINT (long in java). You can require that the application to call your server to get a unique identifier when it is first launched. You can store it on external storage of the device, so that a device where the app is uninstalled and then re-installed will still have the same identifier.