Have a look in Control Panel>Programmes and Features and if it's in the list, uninstall it. I have known it to be there. Afterwards, press the Windows key and R together then into the Run box, type
regedit
and press Enter.
Choose Export from the File menu and note where you're filing the Registry backup you made just in case anything goes wrong.
Search for the word baidu in the Edit>Find menu and keep deleting every entry it finds until it says there are no more.