Deleted Posts Still in Rotation

I had some issues with post names and special characters. I deleted the original post, renamed it and posted it as a new post.

YARPP is listing the new post and the old deleted posts in several cases.

How do I fix this?

http://wordpress.org/extend/plugins/yet-another-related-posts-plugin/