European Commission antitrust regulators are involved in low-level, exploratory talks with Microsoft and Yahoo regarding their search engine deal, according to a Wednesday report. The informal discussions are not yet at a level that would challenge the union, but could lead to a formal review of possible anti-competitive factors in the deal, like Microsoft and Yahoo are facing from US regulators.

In July, Microsoft and Yahoo agreed on a 10-year Internet search deal in an attempt to challenge market leader Google. Less than a week ago, the US Justice Department requested documents from the companies, with the antitrust review expected to be completed sometime in early 2010.

It's not yet known if the European Union will launch a formal probe, and it also remains unknown whether the companies need to get approval from the Commission or from separate national regulators in each EU country.

Yahoo and Microsoft trail Google's 65 percent of all Internet searches in the US, at 19 and 9 percent, respectively. Under the deal, Microsoft's Bing search engine will perform searches started from Yahoo websites, with Yahoo selling ads for the searches. Profits will be shared.