I think a server validation is easiest.
You can use non-blank validation with a value like:
<?php echo(preg_match("/p(ost)?[ |\.]*o(ffice)?[ |\.]*(box)?[ 0-9]*[^[a-z ]]*/",$_POST['addressfieldname'])?"":"1"); ?>
This technique allows you to essentially test for the opposite of a regular expression. You are matching the specific pattern of a po box address instead of matching an address that doesn't have a po box. Then validating that it doesn't match that expression.