ScreenTonic is big in Europe and have sold over a billion page impressions to mobile phones. You can tell they're European because they're not talking about cell phones.
ScreenTonic has significant deals with mobile operators in France (where it's from) and the UK. It does not just sell banner space but copes with text messaging - and has a system to manage and report on those ads.
This is Microsoft on a mobile search/mobile advertising push. It's not a bad move either.
I noticed that Steve Berkowitz, senior vice president of the Online Services Group at Microsoft, talked about this deal and talked about Microsoft putting adverts virtually anywhere. We will see advertising through the Xbox and perhaps even direct to PC advertising too (think of those text lines and banners you already have at the bottom of MSN Messenger).