Technically speaking, archived projects are not searchable via the Advanced Search as we explain in our Guide article: Setting Up a Project in Asana | Product Guide • Asana Product Guide (“Once archived, the project will disappear from everyone’s sidebar and from search results. Though an archived project will not show in search by name, its individual tasks will still appear in search results.”)
That said, this wasn’t always the case; for a while archived projects did appear into Search results, but this was unfortunately because of a Bug, not because of an expected behavior. The bug (which had to do with how we were indexing the search) has since been fixed, which explains why you’re not able to search your archived projects anymore. I completely understand that this change is painful; for the time being, the best advice I can give you is to search through the “Archived projects” option, although I can appreciate that with hundreds or thousands of projects this is not the most convenient. Also, bear in mind that a task doesn’t inherit the “archivedness” of its project, so technically you can search archived tasks via the Advanced Search, it might be a quicker way to get your hands on an archived project. Again I’m conscious this is not ideal, but it might be a good workaround for the time being.