Automatically Replace Old Permalinks With Postname

I’m looking for a plug-in or bit of php that will go through about 300 posts that use hyperlinks in the format:v

<a href="http://mysite.com/?p=3592">

and automatically replace them with their %postname% pretty permalink. Eg:

<a href="http://mysite.com/my-post-about-whatever">

For whatever reason, these posts don’t auto-magically do this when we changed Permalink structure so we’re currently going through one by one. Thousands.

I’m wondering is this is because we’re using a Custom Post Type?

OR, is there a problem with the way we set up the taxonomy that prevents the automatic rewrite? If so, can someone provide some suggestions. Here’s our taxonomy for this Custom Post Type (docs)

//helpdocs taxonomy
add_action( 'init', 'create_docs_post_type' );
function create_docs_post_type() {
	$labels = array(
		'name' => __( 'Documentation' ),
		'singular_name' => __( 'Documentation' )
  );
	$args = array(
    'labels' => $labels,
    'public' => true,
    'publicly_queryable' => true,
    'show_ui' => true,
    'show_in_menu' => true,
    'query_var' => true,
    'rewrite' => true,
    'capability_type' => 'page',
    'has_archive' => true,
    'hierarchical' => true,
    'menu_position' => 50,
    'supports' => array( 'title', 'editor', 'author', 'thumbnail', 'excerpt', 'comments', 'custom-fields', 'revisions','page-attributes','post-formats' )
  ); 	

	register_post_type( 'docs', $args);
}
function docs_init() {
	// create a new taxonomy
	register_taxonomy(
		'docs_tax',
		'docs',
		array(
			'label' => __( 'Documentation_Tax' ),
			'sort' => true,
			'args' => array( 'orderby' => 'term_order' ),
	    'hierarchical' => true,
			'rewrite' => array( 'slug' => 'docs' )

		)
	);
}
add_action( 'init', 'docs_init' );

TIA,

—JC