harikaramAfter not much luck finding a simple way of doing this sans plugin, I did some investigating in the code and found a simple way to fork your 404 template into a true 404 and a separate one for private posts...
http://www.club15cc.com/post/12111588828/wordpress-private-post-404
Hope this saves someone a few minutes...
