Remove McAfee Safe Search bar
Open a terminal, and run:

cd /Library/Internet\ Plug-Ins
ls


Does it show "something something McAfee"?

If yes, try moving it somewhere else (to be able to restore it later, if something goes wrong), replace McAfeeFooBar with the actual name (you can press tab to complete the name):

mv McAfeeFooBar ~/
killall Safari


and start Safari again. If the Toolbar is gone and McAfee still works, you're done!

If you get something along the lines of "permission denied" while trying the mv command, prepend it by sudo and enter your password when requested.

If this doesn't lead to the desired effect, or McAfee breaks, revert your changes by typing

cd
mv McAfeeFooBar /Library/Internet\ Plug-Ins/


again prepending the mv command with sudo if necessary.