Hello,
searching in all versions is not supported in a default Alfresco installation or with any addons I know of. It is theoretically possible but requires some advanced configuration and customization/development to add in.
I.e. the SOLR server of Alfresco already indexes the "archive" (trash) of Alfresco and allows (limited) search on it, and this could be extended to include the version store as well. Major issues to deal with would include permission / ACL indexing and how to present the results in a way that is easy to grasp by end users.
There are no steps on how you can do this that I can give you out of hand, because as far as I know it has not been done before (including myself) and I have only a rough concept of how I would approach this in my head.
Regards
Axel
