Is there an efficient way to dermine whether a node can be viewed by all users?
If you are needing to check node_access records, then you may be able to examine them similarly to how devel_node_access does.  In the end, all nodes have grants added to the node_access table, so if there are grants that deny or restrictively add access, then you can probably see it there.

Another option would be to have a dummy account that is an authenticated user, and used as the test case.  This will fail, of course, if you need to detect grant rules that deny access to authenticated users who would otherwise be entitled.  It's a sticky situation.

The hardest part about this question is that it seems as though you are looking for a general solution to a specific problem, and I'm not quite sure that a general solution exists.