If you use Windows XP or below you can go to Start > Control Panel > Add or Remove Programs. In the Currently installed programs box, click on the IncrediMail program and then click Remove.
If you have Windows Vista or above you need to go to Start > Control Panel > Programs > Programs and Features. Select the IncrediMail application and click on Uninstall.
After that, try running AdwCleaner to make sure that there are no leftover rogue registry keys or toolbars in your system and download and install the latest version of the application from the official web page. Also, make sure that your security program doesn't block IncrediMail connection. Check the FAQ section for further details.