I am looking for a way a way to search my fileshare and find all xls files
that have MS Query queries embedded.

When we create queries in Excel we do not save the queries as external files
(DQYs). So, unfortunately I cannot just search for all DQYs and return a
corresponding list of xls filenames.