Just open up your registry and check if any odd programs added themselves to start up. If they did just delete the entry.
You don't need to format your hd. Just find the program(server of the backdoor) on your computer and delete it. Most likely it added itself to startup by adding a string in the registry. Delete that!