regarding the closed thread: http://wordpress.org/support/topic/removing-old-slugs-permalink-from-database?replies=3
Here the post that explains: http://jeremyrandall.com/technology/tips/removing-old-urls-slugs-from-wordpress-posts
and here my additions:
go into PHPMyAdmin with your WP DB open
choose the Tab "SQL"
put the first SQL-statement in the text-box ("select * from ....")
next the proper entry show up already, choose the one you want to delete and search for the delete button (is at the bottom of the list-box).
Now - this alone didnt do it for me, it still didnt work if I deleted the redirections in the table. I used the slug I wanted to remove as SEARCH-TERM in PHPMYADMIN (open PHPMYADMIN and click on the Tab "Search", that is in about the middle of the top tabs, enter the slug you want to remove, then you get a list of all database table-entries where this text shows up).
I opened WP_POSTS and found a post that was already marked "trash" in post_status (field of the post) that still hat the POST_NAME of the slug I wanted to remove. So I renamed right in PHPMYADMIN the post_name to "OLDNAME-trash", that did it.
the table wp_blc_links is just a table that stores broken links.