AdMob returning ClassNotFoundException

I am trying to integrate AdMob in my Unity app but am getting

java.lang.ClassNotFoundException: com.google.android.gms.ads.MobileAds

I used the PlayServicesResolver and it says it finished successfully. Nevertheless, it doesn't work. I made sure I have the latest version of the resolver.

I even tried doing a Force Resolve.

I noticed that during the resolve process a list of play service packages appear for a few moments in the plugins/android folder but they then disappear.

I am using Unity version 2018.1.4.f1

I also tried exporting the app as an AndroidStudio app. Looking at the Gradle file I can see there is no reference anywhere to Play Services.

What am I missing?