If I have "Collect Payment Before Approval" enabled on my site, does that mean that orders must be paid before they are approved?

No, it only means that the orders can be paid before they are approved. The site setting "Collect Payment Before Approval" only allows to collect payments before the order is approved, but it is not a requirement. Pressero shows the payment form on a checkout, but even if the payment fails Pressero creates a pending order and this order could be paid or approved in any priority (paid then approved or approved then paid). The order will still be pending until it is approved and paid. Once the order is approved and paid, then it will become a finalized order.
 
Current documentation on how the ordering process behaves following changes in Summer of 2021, can be found at article Ch. 004c. Pending.