// Place in 404.php and load subtemplate accordingly
global $wp_query, $wpdb;
if ( count($wpdb->get_results($wp_query->request)) > 0 )
echo 'private post';
WordPress WP_Query’s get_posts() method takes a somewhat draconian approach to private posts on single and page views and strips them from the results even if you specify you want them with the query parameters. With it, goes the ability to distinguish between private pages and those which are true 404s. The snippet overcomes this and allows you to fork the page into two.
Extra bonus points to anyone who points out how I can use an action to direct private posts would-be-404s to another template…