Also what McAfee products do you have deployed?
Obviously VSE, but do you have HIPS, Site Advisor, Web Filtering? Do you have any McAfee firewall appliances filtering traffic at the gateway?
If you think it's VSE causing the issue then what policies have you configured in ePO? Have you tried reverting back to the 'McAfee Default' policies in ePO?
It sounds like a networking or firewall issue.
Let's consider eliminating some of the variables.
You can start Internet Explorer manually, and in safe mode:
Open a cmd console:
Start > type or run 'cmd' > Ctrl-Shift-Enter (Answer Yes or Continue, if UAC is requested; give the administrator password if requested).
"%ProgramFiles%\Internet Explorer\iexplore.exe" -extoff
This should start IE without any add-ons or programs that could interfere. Check access to your searches.
If the search fails, then the problem is more likely a networking issue. Perhaps a firewall issue.
If your searches work, close IE and restart IE normally. Recheck your search. If that fails, then the problem is within IE.
Does you or your business have a 'gateway appliance' of any kind?
Is the problem temporary (short lived) or consistent over time?
Let us know how you are doing.