It looks like you didn't just download that Emoticons plugin, but you also installed it.
Since Mail still complains about it, your attempt to remove it didn't quite succeed.
To find out what's going on, start by quitting Mail if it's running. Next you want to check the folder 'Bundles' in the affected account's Library/Mail folder to see if there's still an Emoticons holdout around. Note that there may be both a 'Bundles' and a 'Bundles(Disabled)' folder; check them both.
A quick way to get to that Mail folder is to select the 'Go To Folder...' menu item from the Finder's 'Go' pulldown menu, paste the path ~/Library/Mail/ in the 'Go To Folder...' text entry box, and hit Go. Depending on your Mac's visibility settings, you may have to hit the Apple-Shift-G keys to make the Library folder visible.
If you find Emoticons related files (like .mailbundle), drag them to the desktop. Next, test if that Mail warning still occurs by logging out/logging in again, or restarting your Mac. If things are OK, move the plugin file(s) to the Trash and empty that.
If this procedure turns up no results or won't work, please report back.
