Graceful Degradation is still a valid concept foundationally, but it's become a bit dated in practice. Modern frameworks have allowed a lot more flexibility in not only the platforms deployable to, but the range of errors handleable when bad/missing data returns. Treating unknown calls returned from a service driven UI begins in the user story writing and design phase. You just have to know what you want it to do.
Without taking away from anything laid in the foundations of Graceful Degradation, you might begin more simply by writing user stories that handle situations you are concerned about. Using your 'Search' example, a User Story might sound like this:
As a Stack Overflow user I want to be able to search topics, so that I
can find threads of interest to me.
AC1 - Given the search engine returns bad or missing status, when I
browse Stack Overflow, then show page components that are
You could refine this to a fine level of granularity, so that the page will resolve until a certain critical level of usability is gone. You could also define specific 'oops' situations where you would not want to provide any bad experience due to bad/missing service information.
The best thing to take away from the Graceful Degradation concept is the notion of requirements > design > prototyping > implementation. The discipline is in thinking through the errors before they happen - not reacting to them after.