I still find it weird. In Windows, if you want to find a document called "Bank account informations.doc": "bank account", "account bank" or "bank informations" in the search box will give the same results. It is a search by word, not by string, that makes more sense IMO, particularly if two words are switched like "theme pokemon".
The difficulties are sorted by date too? Tell me if you see it differently, but as far as I am concerned, when I sort by date, I sort by "date of discovery of the song". I really don't care about the date of creation of the hardest difficulty, and honestly I do not see who could be interested by that... Thus, a classic sorting by star difficulty seems more logical.
It's not weird. It's the same as typing keywords into search bars on sites. It's not going to search EXACTLY in the order you put the search query in, because you probably don't know EXACTLY what you looking for and want to find more stuff related to your search.
What is most likely happening is the search engine searches for both the song names and the tags.
If your search does not match a song name exactly, then it will not display. If the song contains those tags (When you add a space, say, Pokemon Theme, There are 2 tags. The tags being Pokemon and Theme) then it will display the song.
What most likely happened is this.
When you searched pokemon theme, it listed the songs named Pokemon theme because it matches the first search rule that I listed.
When you searched Theme Pokemon, it searched their tags, but the author probably didn't include "Pokemon" and "Theme" into the tags, so the searches that were named pokemon theme were not listed.
This post is a complete guess, but it makes enough sense that it's probably true.