If the service even provides such header or 429 status code at that. They could provide the 418 status code for fun. In this case – without checking the form implementation – I can assume that it provides a JSON response rather than a text response meant to be thrown into the DOM. Grabbing data from JSON is naturally easier but you could use a DOMParser for text content itself if it's sufficiently consistent.

The other thing about "waiting" is that bots may not want to do that, or maybe some sort of deadline is sooner than such waiting would allow.

To me, requiring a unique key to be input with the search, that is created after X amount of time (both provided by the initial response and increasing exponentially for subsequent requests) seems like it could be sufficient. If the next request is sooner than X then block them for Y amount of time for attempting to bypass allowable behavior. Allow like 5-10 emails then implement the wait-based functionality so that most non-bots would be fine. After all we're talking about blocking an endpoint only ever meant to be used via the website by actual users, typically they are not trying to check thousands of emails super fast.