In the last stage, a full DWIM-AI would do the matches. ;)
I once worked on what we called DYM tools (for "Did You Mean"). The goal was to assist native English speakers who were learning a second language find words they heard, in that language's electronic dictionary. We knew, for example, that native speakers of English have difficulty distinguishing the dental and retroflex consonants of Hindi, so the DYM allowed mismatches of those. A perfect spelling was at the top of the list returned from the dictionary, while a misspelling--such as writing a dental for a retroflex--resulted in the mismatched word being a little lower in the list. We tailored our DYMs for particular target languages (and always for native speakers of English). As you say, getting something like this to work for multiple languages at the same time would be difficult.
"Any self-respecting" -- this is very, very hard. If you are Danish, your keyboard most likely has a way to enter Ø and you would expect Ø and O to be handled as two different letters. However, if an English article mentions the Øresund bridge, it's not unreasonable to expect a search on Oresund to match it. Or, in Hungarian, "kor" means period or age, "kór" means disease and "kör" means circle... but searching for "kor" in Chrome finds all of them. And Unicode won't save you: Ø does not have decomposition rules but ó and ö both do. So the common practice of decomposing - removing marks - recomposing route can either be too little or too much. The upcoming solution for Drupal will allow users to edit remove diacritics rules per language, no other way to do it.
This is Libreoffice taking that path, I know Firefox does the same: https://cgit.freedesktop.org/libreoffice/core/commit/?h=libr... see the icu::Transliterator::createInstance("NFD; [:M:] Remove; NFC", part.