A few issues.
1) The checkout form needs to work with client validation and not server validation. The server validation is a catch-all, but the messages are managed with the jquery validation since the lower section of the page loads with AJAX and the top form itself isn't reloaded, so server validations wouldn't show unless the page reloads.
2) Your pattern matched if the field had PO BOX in it... You wanted the inverse of that to match if it DIDN'T have PO BOX
I was able to solve your issue, but I had to update the jquery.h5validate.js file to allow for more complex pattern matching. Please download a copy of that file. I'll have it updated in the next update, but it may get overwritten in the meantime, so save a backup.
I also added the pattern attribute to the <input> tag and adjusted the pattern so it has the inverse effect (fails if the pattern includes PO BOX).
I also updated the pattern to the same effect in the server validation.