When app is removed from the play store, is it removed from everyone's phone that downloaded it? I woke up this morning and noticed a missing icon for an app.  I don't know which app; it's just a missing position in a grid of icons.  It made me wonder...  When app is removed from the Play store, is it removed from everyone's phone that downloaded it?  Does having auto-update matter at all, and in any case, what happens to the user data?  Will I receive an email notification of the app's removal?

It's disconcerting that someone else could have uninstall power over apps on my phone.

Phone: Samsung Galaxy S3 SCH-I535 Running Android 4.4.2
In general the answer is no - however Google do have the capability of remotely removing apps (i.e. Malware)  from everyone's device as required, and if they do so they will provide you with a notification.

This was explained by Rich Cannings, Android Security Lead in an Android Developers blog post, back in 2010:-


  ... In cases where users may have installed a malicious application that poses a threat, we’ve also developed technologies and processes to remotely remove an installed application from devices. If an application is removed in this way, users will receive a notification on their phone.
  
  Recently, we became aware of two free applications built by a security researcher for research purposes ... [a]fter the researcher voluntarily removed these applications from Android Market, we decided, per the Android Market Terms of Service, to exercise our remote application removal feature on the remaining installed copies to complete the cleanup.
  
  ... a dangerous application could be removed from active circulation in a rapid and scalable manner to prevent further exposure to users. While we hope to not have to use it, we know that we have the capability to take swift action on behalf of users’ safety when needed. ...


This was then used to remove 60 malicious  applications back in 2011


  On Tuesday evening, the Android team was made aware of a number of malicious applications published to Android Market. Within minutes of becoming aware, we identified and removed the malicious applications. ... But given the nature of the exploits, the attacker(s) could access other data, which is why we’ve taken a number of steps to protect those who downloaded a malicious application:
  
  We removed the malicious applications from Android Market, suspended the associated developer accounts, and contacted law enforcement about the attack.
  We are remotely removing the malicious applications from affected devices. This remote application removal feature is one of many security controls the Android team can use to help protect users from malicious applications. ...