Если вы посмотрите на самый верх страницы, на которую вы ссылались, они заметят, что API устарел, а количество поисковых запросов, которые вы можете сделать, ограничено.
Однако, если вам абсолютно НЕОБХОДИМО использовать этот API вместо API пользовательского поиска, как предлагает Google, есть несколько шагов по устранению неполадок, которые вы можете предпринять:
1) Убедитесь, что ваш ключ API уникален для проекта, и ограниченное количество разрешенных запросов не используется каким-либо другим приложением.
2) Google выполняет (делала?) Фильтрацию имен хостов, чтобы один компьютер не использовал все запросы API. Возможно, вам удастся переместить запросы в Javascript вместо Java - по сути, переместите запрос с сервера на клиент.
3) Попробуйте использовать именованный бэкэнд ( Java Backends )