It wasn’t that Apple removed Google Maps from App Store. Maps.app on iPhone were using Google Maps data prior to iOS 6. Google Maps the app didn’t existed when Apple switched to use Apple Maps.

Timeline:

Sep 19, 2012 - iOS 6

Dec 13, 2012 - Google Maps launched on App Store