You know there is this problem with Magento 1.4.* and 1.5.*, if you are using Paypal Express as payment method and your customer is a new one, when she/he complete the order this is without account association (Customer Group 0 USER NOT LOGGED IN) and the new customer is not created.
To solve this problem you have to install this useful extension: https://github.com/onestepcheckout/PaypalRegister
Follow the README and finally you can get registered users with Paypal Express too.