When you open System Restore, you are presented with a list of available restore points.
Below the list, on the lower right, is a button which says "Scan for affected programs"
If you highlight one of the restore points on the list, and then click on that button, system restore will run a scan of you system - which may take a few minutes - after which you will be presented with a list of software that will be removed, along with another list of software which will be restored. This will give you a good idea of exactly what to expect.
Take a look and see if there are any elements relating to Bing on that list.
If you've run any updates to your programs, software, anti-virus definitions, etc - those may need to be re-installed.
However, your system will be restored to the condition it was prior to making any changes - so you should be able to go back and remove Bing properly via the Windows un-install feature in Control Panel.
Also - if it does not work, you will be able to completely "undo" the system restore and return your system back to where it is right now.
Hope this helps.