If the post/page was previously published, and you changed the slug when you edited the page, the old slug gets put into the post meta table with the name _wp_old_slug. So you can use get_post_meta( $post->ID, '_wp_old_slug', $single = false ); to retrieve the former slug(s). I see no reason this wouldn’t work with CPTs, as they’re just a special type of post.
