Just break the Unspecified MCID down by Cities or Countries could already be insightful.
Just mentioning, should the MCID not be set all the time when the Visitor ID Service is present?
Assuming that you are mapping this somehow in your tag manager, where do you get this information from? The s_ecid cookie?
But then, why is the MCID containing different formats? Entries 3. and 4. are valid ECID formats, everything else is not.
Are you potentially using some APIs to push data to your report suite, like the Bulk Data Insertion API or explicitly setting the s.VisitorID (which Adobe advises not to do)?

Thanks All for the inputs.
So many aspects are put to debug this scenario in different ways. Recently, extracted a raw (data feed) report, which shows that visitorID values ware changing frequently and then saw the extension we found this configuration inside the Adobe Analytics extension > custom variable:

When a user opts in - we see correct form of MCID and when a user opts-out, the wrong pattern as seen in previous screenshots.
So, the custom or manual configuration of visitor ID should be removed or modified? So, that visitor should not be counted new every time they come back on the site.