Even Google has this problem with some common words. If you type "Nudel", which is German for noodle, into the Google search box, you won't get auto-complete entries presumably because it contains the word "nude". This happens even on the German Google version (?hl=de).

Interestingly, it seems that Bing does a better job of separating "Nudel" and "nude" as it does offer appropriate auto-complete entries. I'm not sure how widespread this problem is and how Google and Bing compare on other search terms, though, since I only randomly stumbled upon this issue while searching for recipes.