The solution is what ROMs do since cyanogen was taken to task by google for bundling google apps with his ROMs. They let you download the google apps you want,

The solution is what ROMs do since cyanogen was taken to task by google for bundling google apps with his ROMs. They let you download the google apps you want, or none. If they allowed clean installs for stock google images and the customer could choose which Google services/apps to install factory resets wouldn't be an issue.