They could also try to claim trademark infringement based on the fact that Microsoft is hijacking searches for the keyword “google”. Courts have previously rejected trademark claims when a company takes out search ads using its competitor’s name as a keyword, but Google could argue that what Microsoft is doing here is more deceptive than that.
(IANAL and have only passing familiarity, but I’m fairly confident in the above.)