Unity Ads plugin works perfectly fine in the editor, but fails in android

I am facing an issue with the Unity Ads plugin. It seems to work perfectly fine in the editor but initialization fails in the Android build.

While debugging, I can see these 2 errors for some reason.
2020-11-28 07:44:40.375 14485-14508/? E/Unity: Unable to find UnityAdsAndroidPlugin
2020-11-28 07:44:40.375 14485-14508/? E/Unity: Unable to find UnityAds

But later I can also see the logs:
2020-11-28 07:44:43.072 14485-14508/? I/UnityAds: com.unity3d.services.UnityServices.initialize() (line:126) :: Initializing Unity Services 3.5.1 (3510) with game id XXXXXXX in test mode
2020-11-28 07:44:43.075 14485-14508/? I/UnityAds: com.unity3d.services.UnityServices.initialize() (line:146) :: Unity Services environment check OK

When I try to show any type of ad, it throws an error log saying: Interstitial Ad not ready or Video Ad not ready.

I initially tried the Advertisement plugin from Package Manager. Later I removed it completely and tried the Unity Monetization package from Asset Store.

I had read somewhere that the project version needs to be changed. I tried doing that as well. Initially, I was working with 2020.1.11. I changed that to 2019.4.15(LTS). Still no luck.

to use unity ads : Unity Ads 2020 | Adding Rewarded Advertisement - YouTube
to use admob ads : How to Monetize your game with Admob Ads in Unity | Admob Ads in Unity - YouTube