Recurring Profile – Does It Create a New Order on Every Billing Cycle?

In EE, there's a setting in System > Configuration > Sales > Payment Methods > Paypal Express Checkout > Advanced Settings > Billing Agreement Signup, which you can set (looks like default may be 'Never'). Hope that helps...

A successful payment does not create an order from a quotation. The customer confirmation creates the order. The payment is unrelated to this process. Think about COD, ship after received payment, invoiced orders in a b2b system. These are all examples of orders being created before the payment is received.

The customer has created this recurring profile and thus the intent has already been expressed to receive the goods and make the payment. It is a valid order. It should be created with status "awaiting payment", if your method cannot verify payment immediately and processed by the back office accordingly.