I really hope Incredimail can solve that issue. Actually i am sure they will (Microsoft might see here an opportunity)
Google can be a fantastic business partner but if for some reason you loose it it may impact significantly your operations. Not only from a revenue point of view but also from a distribution point of view.
A lot of startups are building their distribution strategy on Google page rank and their ability to be well ranked in search results. This SEM strategy is good and even cheap in the short term but risky if Google changes suddenly its algorithm or decides to takes you off the index. This happened recently with lots of startups and services that were using abusively internal backlinks to increase their page rank.
The real challenge is to become a destination site not staying a Google shadow
Update: Mike at TechCrunch has published a note about this too. He mentions this could have to do with fraud. But nothing is confirmed for now.
Update 2 : i just had a chat with one of the founders of Incredimail which confirmed that as a public company they cannot disclose the reason why this all happened but that this is not related to a fraud issue. Also confirmed that in a few days all will be sorted out (with or withouth google?)