I scrapped an old website in March and replaced it entirely. As is common, I expected many old links and to exist all over the web, and in people's bookmarks and emails, etc. There were hundreds of pages and the structure is different enough that it was not considered to map every old URL to a new page. So instead of showing a 404 page, we decided to route all invalid links to the homepage. So my site does give a 404 error, but then is rerouted to the home page with a 301 redirect.
I submitted my new site maps to Bing, and it has recrawled the site, but not a single link in the results Bing search results has been updated in over 3 months.
Even though manually deleting hundreds of URLs would be a huge pain, it's not even possible. I get: "The URL you submitted still works on the web and isn’t a broken link. You can only request an outdated cache removal for this page. Please enter a word that appears in the cached version of the page but no longer appears on the web page."
So, if a site is entirely replaced or has a massive overhaul, it's forever impossible to update it with Bing? It's a catch 22, because sites like Bing having old URLs are exactly why redirects are required.