> Though, annoyingly, you can't use the search function without data.

Have you tried this recently? I just did a family vacation in Death Valley and used Google Maps offline exclusively. Search worked fine.