I solved the problem myself.
Under the page - partner.microsoft.com where the MPN ID is approved, I had to go to User Management tab in the left side, and then click a link to become administrator and owner which is shown there. By default, when the account is created, it is only email-authorized, but in order for it to become domain-verified, you also have to make it as administrator, after it is created initially.
Once I clicked that link, it presented a screen with the TXT value for DNS entry which I added it to my domain and after clicking the "Verify" button, it worked and it converted my account into Account admin, Referrals admin, MPN partner admin, Owner. Some of the steps and button names are from memory as I didn't document them along the way but this is very much how the process went.
Then I was able to add verified MPN ID to the application created in the portal.azure.com (Branding & properties section) and now it shows the verified blue badge.
One pitfall I had is that also under the partner.microsoft.com - User management tab - Azure AD Applications sub-tab, I added my application. That was a mistake - don't do that. When I tried to add MPN ID under portal.azure.com it warned me that I was not the owner. After removing the app from Azure AD Applications in the partner.microsoft.com it worked then and I was able to add MPN ID under the portal.azure.com.
This process could certainly be much easier than it is, it is very unintuitive as it is IMHO. There are many ways to fail, many unnecessary steps like linking the partner account with azure AD portal account, it is not clearly explained and I spent days to locate what basically took 2 minutes once I knew where to look. A good video tutorial by Microsoft would be more helpful.
