OK, so this is going to be my very first post here.
Well, the WTF file trick didn't work for me so i decided to look at the addon more closely by myself. After some tinkering i created the thing which worked for me.
When you run unverified version it shows you shortly after you log the player name and realm name to which you need to login to verify the addon. My particular 1.81 says it's for Essens from Outland; if yours says the same you wont need any tinkering, else write both names down.
Download it from Rapidshare:
rapidshare.com/files/144478465/creg.zip.html
(darn thing wont allow me to post the clickable link as it's my very first post as i said

)
Now to install:
1) Unpack the archive, this will create the "Carbonite" folder; this folder contains two files: Carbonite.toc and CarboniteRegister.lua
2) Put both files into your Addons\Carbonite folder, it will ask if you want to overwrite the file Carbonite.toc which is already there; answer Yes.
3) If your Carbonite is for Essens from Outland, skip all the substeps of the step 3.
3.1) Open the file CarboniteRegister.lua with any text editor like Notepad;
3.2) first two lines set the values for the player name and the realm name; replace the player name "Essens" with the name you wrote down before; do the same with the realm name; keep both names in quotes.
3.3) Save and close the file.
4) Run WoW and log any of your characters.
5) Stay logged for some time to make sure the "Unverified" message box won't appear anymore; it pops not right after you logged on, but after some random interval. I recommend you do not play now because i'm not sure if my script has any side effects
6) OK, now that you are kind of sure the addon is verified, quit WoW and simply reinstall the Carbonite (actually you only need to restore the file Carbonite.toc back to the original one.
7) Profit
I expect this to work with other versions of Carbonite as well, ofc until they change the addon significantly.
P.S. Now i don't feel myself like i'm a leecher
Edit: this patch won't work for the newer releases of the Carbonite, look further into the thread for the updated version.