> I know this is probably a silly question, but would there be any way to modify SSH to enforce using passwords on the public keys rather than rely on people following a policy document?
Nope.
> I can't imagine any way to do this with 100% effectiveness because you'd have to trust the client side to tell you the truth and a determined policy violator could simply build a custom ssh client that would lie to the server.
Ya. Your right.
This is much much better for large orginizations to disable public key authorization support and use Kerberos instead.