Как лучше всего кешировать запросы с учетом строки поиска на фотостоках с API в PHP?
Кэшируйте через клиента, исполняя запрос к API из браузера, а результат - отправляйте себе на бэкенд и там - кешируете, группируя одинаковые ответы на различные запросы в единую группу.

Если это невозможно - группируйте поисковые запросы и привязывайте результат к такой группе.
Для отображения - находите группу для запроса и достаёте ответ из кэша этой группы.
Привязка простая: "один-ко-многим": ответID->запросы.

Дополнительно:
Можно проставлять "веса" на каждое слово в запросе и составить свой словарь синонимов, чтобы выдавать релевантные результаты из своего кэша на запросы, которые похожи на предыдущие, но которые не отправлялись ни разу на API фотохостинга.
Иными словами: сделать свой промежуточный поиск до поиска в фотохостинге через API.
про etag почитай