Can App stores remove/have exceptions about what is allowed or not as
Yes, they can, because they're businesses, not public services. Both Apple and Google have clear, legally binding TOS statements that outline your participation in their businesses: I.e., Google's: http://play.google.com/intl/en_us/about/play-terms.html
It is worth noting that Google reserves the right to change terms at
Of course they can, and they do from time to time. That's part of the TOS you agree to: "Changes to these Terms." Any App developer, game dev, musician, etc., who wants to be on Play has to abide by every line Google's TOS. It's a contract.
However, they have terms, and other companies might put millions into
developing something according Google's terms, but that Google might
not like and want to kick out after some time.
It is solely that business's choice to put millions into developing something in an attempt to get that product in Google Play. Google is not obligated in any way to accept anything into Play, no matter the money or the business involved.
Can the company take legal action against Google for removing
something by proving that it is not against any law or their terms of
Sure, you can take Google to court for disallowing a product from Play or removing an accepted product from Play. You will need to prove via a preponderance of evidence that the product does not violate any points in the TOS. How much money do you have to fight Google?