I think the solution is amazingly simple here:
You’re just missing a single line of code in your ajax callback, namely:
global $post;
where I assume you’re using:
$post = get_post( $post_id );
The reason is that there’s a global post check in the WP_Embed::shortcode() method.
More details in my answer here.