If it is active from being included on the startup group you can use two methods to shut it down. The quick way is to press the ctrl-alt-del buttons together or right click on the task bar to bring up the task manager. You would highlight the items seen there for messenger and press the end process button.
A second option is restart the system in safe mode to insure that only the basics are running and try there for removal. The third and often needed method is to type in "msconfig" at the Run prompt off of the Start menu and uncheck the messenger listings there and in the services tab which insures after a restart that no part loads up. These are three immediate ideas to go with to remove the service completely.