I finally decided to change my permalinks to more standard types, such as http://www.thepiratescove.us/2008/04/01/retro-pirates-cove-moonbat-underwear/Â versus the old type http://www.thepiratescove.us/?p=5434. Much better for search engines and when linking to other sites.
In order to accomplish this and still have all the old links to other sites and throughout the Interwebz, I am using a plugin called Permalinks Move Permanently. What this does
Right before the old permalink generates a 404, this simple plugin grabs the slug from the end of the request and checks if there’s a post with this slug living somewhere else on your blog. If so, it will generate a “301 Moved Permanently” error, and forward your user to the new location of your post. It’s simple, but effective.
I initially tried changing the permalinks with my test site, and, instead of 404’s, I was getting 500 errors. With the plugin, it redirected to the correct posts. Cool!

