Interesting. I'm still getting times around 20 seconds, but my account isn't very old and doesn't have a lot of posts.

You might not need a workflow for this. Take a look in NetSuite Help Center at SuiteCloud (Customization, Scripting, and Web Services) > SuiteBuilder (Customization) > Custom Fields > Creating a Custom Field > Setting Sourcing Criteria.

As far as I know, the order status is read-only. The status will change when the order actually is billed.

I am by no means an expert on this, but my understanding is that for server-side stuff (like After Record Submit) you use Oracle SQL functions, and for user-side stuff (like After Field Edit) you use JavaScript. So you would need to replace REGEXP_INSTR with a JavaScript Regular Expression.

Try going to Documents > Templates > Email Templates > New. There you can use the text editor "Field Type" and "Insert Field" fields to help design your email. After saving, select it in the workflow with the "Use Template" option rather than the "Custom" option.