Moving posts from one category to another – when do old URLs fall off

To increase site navigability, I added some new categories and deleted some old categories. I am now finding links to the same posts that were in Uncategorized to both the Uncategorized (original category) and to the newly created category. When I edited these posts I watched WP update the URLs. I don’t know how this is possible. I use a redirect that sends all unfound pages to my index page. I don’t want two URLs that go to the same post.
what do I do to get rid of the old URLs and only have the new URLs.
Do I run them through Google Webmaster URL removal tool.
How long does it take for the old (undesired) URLs to go away and leave me with only the new (desired) URLs.
I apologize for any redundancy, I don’t know the proper terms to express what I want.