You can use the get_post_types function to fetch and search through the registered post types up to that point (the init hook where you would normally register the custom post type). You can possibly use a later hook like wp_loaded to do this check before trying to register the post type in case some other (not related to any of yours) plugin might have registered it already.
