I looked into this. The cause seems to be that the search only checks for the 300 releases with a title that best matches the given one, and then it checks which of those have a medium with the right number of tracks. In this case, the Japanese releases are being found by a search which checks for the 600 releases with the closest title - but 500 for example still does not find them. On a direct search for NOSTALGIA, these appear on page 25.
Ideally this search would not have a limit at all, but that will probably cause timeouts? We could:
1) Give this search a higher limit (but that might not help with all searches)
2) Add a text that says "For performance issues, this checks only the top 300 releases matching your search. To ensure a better result, search for the full release title or as close to it as possible. You can also search manually and paste the link to the release here." or something, with "search manually" pointing to the indexed search.
3) See if we can use the indexed search directly here, now that it updates very quickly anyway... https://musicbrainz.org/search?query=NOSTALGIA+AND+tracksmedium%3A40&type=release&limit=25&method=advanced does find all of the options without any issues.
We should make sure whether the limit is needed at all nowadays (it was added 16 years ago). "a good route would be to print the query from Perl and run it directly on hendrix with EXPLAIN ANALYZE" says bitmap (with and without "$hard_search_limit").