Yes, they can; they can have the older app say "you need to upgrade your app" (likely with a 60 or 90 day grace period), and put the new one on the play store. Alternatively, maybe their native client already falls back on an HTML5 alternative on a cue from their server - I have no idea.

What is clear from this debacle, though, is that Microsoft was unable to write their app according to Google's guidelines, and then took 3 months and still couldn't fix it - which means that Google definitely cannot expect them to upgrade to newer APIs ever - so it doesn't seem onerous to require them to actually use the official API now.