Document ID not searching all sites.

In the last 2 weeks or so Document ID's in our tenant will no longer search all sites and are giving an error.  

No documents with the ID TMF7YV4PPCSC-377269073-29814 were found in this site collection

Is anyone else experiencing this?  

To recreate:

1. have 2 sites with document id's enabled
2. create a document in second site such as https://tenant.sharepoint.com/sites/testsite/library/test.xls
3. copy document id of test.xls
4. Document id will be formatted https://tenant.sharepoint.com/sites/testsite/library/test.xlshttps://tenant.sharepoitn.com/_layouts/15/DocIdRedir.aspx?ID=%3cDocumenthttps://tenant.sharepoint.com/sites/testsite/library/test.xls
5. remove site information so link now reads
   https://tenant.sharepoint.com/_layouts/15/DocIdRedir.aspx?=<Doucment>

By default the document id link should search all sites as is the default setting instead I get the error message mentioned above.  Worked 2 weeks ago.

I am working with Microsoft on this for last 2 weeks and am not getting anywhere and wanted to see if others are having this issue.