On the way, I discovered a tool called "sc.exe". Deleting a service has never become easier that that command :D
1. Start->Run->cmd
2. sc delete service_name - where service_name is the service to be removed.
To find the service name,
1. Start->Run->services.msc
2. Find the service. The 1st column contains the service name. Use this in the sc command.
Read more about the sc.exe command.
Bye!