Is it possible to use REGEX in a Workflow? Goal is to trigger a work flow if a Sales Orders Shipping Address contains a PO BOX, but I want to use REGEX to capture a few different formats that it may come in as...

Yes, you can use a formula condition and that should allow you to use REGEXP_INSTR

You can also create a saved search using that criteria (or any other way you've found to meet that criteria) then use that saved search as a condition for a transition or action