Consider the case when the user is asked to select one item from a fixed list.
If the list contains more than a dozen items, an autocomplete / typeahead type widget has proven itself to be very user-friendly and quick to use. You type a few letters and a popup appears—or is updated—with relevant matches, without stealing your focus from the search box. When you find what you are looking for, you can click on it from the popup, or select it with arrow keys and confirm with Enter.
When the list has less than a couple hundred items, the best HTML-only graceful degradation is a simple select box. The list of countries (206 as of this writing) is the classical example that's at the limit of usability for a select box. Anything longer than that and it gets heavy to download and render and cumbersome to use.
So what is a good HTML-only graceful degradation for a typeahead / autocomplete box, when the list contains thousands of items?
But what if the original form contains more than one typeahead box? Would you show them a sequence of intermediate steps, one to refine each selection?
Replace the typeahead boxes with buttons.* Each button will submit the partial form (to be stored on the server in some temporary or session storage) and show a page with all the tools to search for items and make a selection. When the user makes their selection, go back to the half-filled form and let them continue.
Replace the typeahead boxes with iframes* (say, 5 to 10 lines tall, as big as a textarea.) Each iframe will let them perform independent searches and selections, which will be stored on the server, without disrupting the main form.
Any other idea?
* Of course, technically it's the opposite: you put the degraded interface in the HTML and then use JS to replace it with the autocomplete.