Custom permalink structure for custom post type results in 404

The problem with the code you’ve posted is that you’re using the timestamp to create the permalink, and using it in add_rewrite_rule as if the timestamp was the post ID of the recipe. The p-parameter in index.php?post_type=recipe&p=$matches[1] is used for passing post ID’s. Thus, WordPress will start looking for a post with an ID like “20140609070153”.

Now I’m not sure why you would want a permalink such as this, but to keep a similar permalink structure that actually works, you could add the ID to the permalink structure, creating, for example, the permalink http://example.com/recipe/21-20140609070153, which is passing the post ID (21) as well.

add_filter( 'post_type_link', 'wpse33551_post_type_link', 1, 3 );

function wpse33551_post_type_link( $link, $post = 0 ) {
    $timestamp = $post->post_date;
    $timestamp = preg_replace("/[^A-Za-z0-9]/", "", $timestamp);

    if ( $post->post_type == 'recipe' ) {
        return home_url( 'recipe/' . $post->ID . '-' . $timestamp );
    }
    else {
        return $link;
    }
}

add_action( 'init', 'wpse33551_rewrites_init' );

function wpse33551_rewrites_init() {
    add_rewrite_rule(
        'recipe/([0-9]+)\-([0-9]+)?$',
        'index.php?post_type=recipe&p=$matches[1]',
        'top'
    );
}

A problem with this solution is that it would yield a valid page for any timestamp appended.

Concluding: I would move to another permalink structure, actually uniquely identifying a post (which a timestamp doesn’t) :-).