Depending on the program you deleted, there may be other files on your system that work with the application. Check your home folder > Library > Preferences for files that might contain settings for the software and remove them. Also check /Library/Application Support and look for a folder that corresponds to the software you deleted. First try moving the folder to your desktop, the install the new software again and test.
Note that if you're removing Illustrator and reinstalling it and you have Photoshop or Acrobat Reader on your machine, DO NOT remove the "Adobe" folder from Application Support unless you are prepared to reinstall all of your Adobe applications.