Try this method Ben :
Manual removal
Please follow the instructions below if you would like to remove WebRebates manually. Please notice that you must follow the instructions very carefully and delete everything that is mentioned. In most cases the removal will fail if one single item is not deleted. If WebRebates remains on your system after stepping through the removal instructions, please double-check by stepping through them again.
Start the registry editor. This is done by clicking Start then Run. (The Run dialog will appear.) Type regedit and click OK. (The registry editor will open.)
Browse to the key:
'HKEY_LOCAL_MACHINE \ SOFTWARE \ Microsoft \ Windows \ CurrentVersion \ Run'
In the right pane, delete the values called 'WebRebates0' and 'WebRebates', if they exists.
Exit the registry editor.
Restart your computer.
Start Windows Explorer and delete:
%ProgramsDir%\Web_Rebates\
%ProgramsDir%\WebRebates
Note: %ProgramsDir% is a variable (?). By default, this is C:\Program Files.
Sorry if this is the method that you have already tried but maybe you have missed a step ?
This has a lot more information about which folders it creates and more things to delete in the registry :
http://securityresponse.symantec.com/avcenter/venc/data/adware.webrebates.html