I think this is related to the opposite problem (customers seeing the logged in message even though they aren't supposed to be logged in) which is described in this thread: http://www.ubercart.org/forum/support/4655/ubercart_not_displaying_corre.... PayPal completes the sale when the payment is received, so the user account is created and the email is sent. However, when the customer comes back to cart/checkout/complete, there was some faulty logic that assumed that orders with users must be logged in.

Now it shows the "existing user" message because there isn't a good way for Ubercart to log them in without their password. Hopefully customers will read their emails.