I had asked this question of ICANN a few years ago, as we were debating this very question in one of the policy lists.
Their answer was that indeed a P.O. Box *is* ok for the WHOIS address.
I found the email exchange archived on the mailing list (Dan Halloran was the ICANN person). You can find it at:
http://www.opensrs.org/archives/disc...0205/0810.html
Q.E.D.
