Assuming no spyware or virus problems, I would think it's being
done at the ISP side.
Edit their HOSTS file to point to Baidu when users use Google,
Yahoo or MSN. Or they don't edit, re-route the whole traffic. But
they would take up significant amount of time and users will notice
it and set up another routing table for it.