Certainly a strange one.
Since you say that the problem also occurs using Android phones, I would try removing anything to do with Google (Toolbar, Chrome etc.). I'd be inclined to use Revo or Smarty uninstallers to make sure that all traces are removed.
Reboot and see if anything has changed.
Also check Services to see if there is anything strange in there. Compare with Black Viper if not sure.