add_filter( '404_template', 't5_redirect_to_category' );
function t5_redirect_to_category( $template )
{
    if ( ! is_404() )
        return $template;
    global $wp_rewrite, $wp_query;
    if ( '/%category%/%postname%/' !== $wp_rewrite->permalink_structure )
        return $template;
    if ( ! $post = get_page_by_path( $wp_query->query['category_name'], OBJECT, 'post' ) )
        return $template;
    $permalink = get_permalink( $post->ID );
    wp_redirect( $permalink, 301 );
    exit;
}