I wonder how they might do this. Possibilities I can think of:
A) Stop releasing Android phones and use WP7 and such (similarly risky, if it's actually something the market wants).
B) Keep using Android but make more deals like the one that put Bing as the unchangeable default search on the Galaxy S.
C) Fork/rebrand Android and make their own derivative.
B seems most likely--same platform so they can benefit from Google's development, but with Google services blocked.