You open Edge, open an InPrivate window, surf to the website you want, close the tab, clear history (a step you should not have to take for InPrivate data, as none should be stored to begin with!) close the browser, reopen the browser, type in the first few letters of the URL, then watch as autocomplete fills in the InPrivate-ly visited address for you.
This, even if you've never used Edge to visit the website except for during that one InPrivate session. This, even after you close the browser, reopen it, clear history, then repeat those steps again and again after making that one InPrivate visit. You can't erase the URL from Edge's history.
It's probably a known bug, and while I sort of put up with it on the Insider Builds (and while there's probably the same sort of hokey fix for it that works with Windows versions going all the way back to Win95 - that is, simply navigate to and manually delete any temp files associated with the URL[s] in question), I have an activated copy of Win 10 Pro that does the same thing, and after a year or so of monkeying around with this, it does get a bit old.
I know at some point - but I haven't paid attention so I'm not sure at which point - the history and cache, despite the bug's persistence within the context of using the computer without any shutdown or restart - will eventually resolve itself, maybe only after said shutdown or restart or else not until after CCleaner runs and clears the Edge Database and cache - this is where I need to start paying more attention, but either way, no one should have to either shut down or restart their computer or else run CCleaner to resolve this issue each time it comes up.
Which makes me wonder, now that I think of it, if Edge clears history at all without taking one or more of the steps above. I'm used to thinking of it as an InPrivate bug, mostly because I use Edge with InPrivate (originally the idea was to save taking extra steps to clear data before closing a browsing session, but that's never worked thanks to how gleefully it not only collects but also retains the very data it's not even supposed to collect).