This is a known problem which we're working on.
You were on the right track with the work-around, by downgrading to < 10.2.

Did you downgrade all packages to the same version? You can't mix and match them.

I have downgraded all play-services-*.aar packages in the Assets/Plugins/Android directory.
After reading your comment, I downgraded also firebase-messaging-10.0.1.aar (by getting the aar directly from the repo) and firebase-common-10.0.1 and firebase-iid-10.0.1 (by extracting the contents of the aars I got from the repo)
I get this error:

firebase: Java class com/google/firebase/FirebaseApp not found. Please verify the AAR which contains the com/google/firebase/FirebaseApp class is included in your app.

It sounds like you're now missing the dependencies.

How are you downgrading? You might want to set the version in the "*deps.cs" files, and you'll still need to use the android jar resolver.

I tried to manually set the version in all the "*deps.cs" files. Now the resolver correctly resolves to 10.0.1 on every dependency in the Assets/Plugins/Android directory. If I execute the quickstart project Firebase Messaging works flawlessly.
On the other hand, when I try to integrate this whole process to the production project I'm working on, I get this error:

03-20 17:05:09.749  7363  7384 I Unity   : NullReferenceException: Object reference not set to an instance of an object
03-20 17:05:09.749  7363  7384 I Unity   :   at Firebase.Internal.InstallRootCerts.InstallDefaultCRLs (System.String resource_name, System.String directory) [0x00000] in <filename unknown>:0 
03-20 17:05:09.749  7363  7384 I Unity   :   at Firebase.Internal.InstallRootCerts.Process (Firebase.FirebaseApp app) [0x00000] in <filename unknown>:0 
03-20 17:05:09.749  7363  7384 I Unity   :   at Firebase.FirebaseApp.CreateAndTrack (Firebase.CreateDelegate createDelegate) [0x00000] in <filename unknown>:0 
03-20 17:05:09.749  7363  7384 I Unity   :   at Firebase.FirebaseApp.Create () [0x00000] in <filename unknown>:0 
03-20 17:05:09.749  7363  7384 I Unity   :   at Firebase.FirebaseApp.get_DefaultInstance () [0x00000] in <filename unknown>:0 
03-20 17:05:09.749  7363  7384 I Unity   :   at Firebase.Messaging.FirebaseMessaging Listener..ctor () [0x00000] in <filename unknown>:0 
03-20 17:05:09.749  7363  7384 I Unity   :   at Firebase.Messaging.FirebaseMessaging Listener.Create () [0x00000] in <filename unknown>:0 
03-20 17:05:09.749  7363  7384 I Unity   :   at Firebase.Messaging.FirebaseMessaging..cctor () [0x00000] in <filename unknown>:0 
03-20 17:05:09.749  7363  7384 I Unity   : Rethrow as TypeInitializationException: An exception was thrown by the type initializer for Firebase.Messaging.FirebaseMessaging

My best guess is that it's happening during the execution of the Firebase.Messaging.FirebaseMessaging.TokenReceived callback.
If you think it's an unrelated issue, I'll close this one.
Thanks.

Did you follow the instructions for setting up your app on the firebase console?
https://firebase.google.com/docs/unity/setup

I'd especially double check the part about setting up your SHA certificate:
https://developers.google.com/android/guides/client-auth

Thanks for your advice. The issue is now solved.
Here are some further details on how to workoround this issue:

• When downgrading the dependencies, most of them are declared in the "*deps.cs" files, but depending on what other plugin you use, they may be declared somewhere else. Searching for the string "VersionHandler" in the whole project will find everytime the Resolver is being used.

• The certificate issue can be solved in "Player Settings -> Other settings" by setting "Stripping Level" to "Disabled".