Кэширование будет моим первым выбором.
Это зависит от сайта, который вы разрабатываете, но не могли бы вы кэшировать все результаты и сообщить пользователям, что это то, что вы сделали - например, «это было верно в 2009-10-08 - нажмите здесь, чтобы обновить»
ОБНОВЛЕНИЕ: Не зная больше о том, какие данные вы получаете от веб-службы и что аудитории вашего сайта сложно понять, что предложить, так как решение будет во многом зависеть от тех, факторы. Вам нужно подумать о своих клиентах, чтобы решить, можете ли вы показать им потенциально устаревшие данные или нет.
Если запросы к веб-службе, как правило, похожи, то следует учитывать возможность того, что кэширование также поможет вам с производительностью и масштабированием, а также с устойчивостью.