OK, I finally figured out what was going on:
If a customer uses the Paypal Express Checkout at the shopping cart and they have not logged in or created an account at the OsCommerce store, then the shipping options are calculated in the background before transferring to Paypal. This is because I've also found out that if Paypal Express Checkout is used and you are using your own OsC shipping modules (I have USPS, UPS and FedEx), the default shipping method is calculated and added into the order total before transferring to Paypal. However, the calculations are also done for all of the other shipping rates/modules you have enabled. That is where the e-mail debug errors with my UPS module come in.
Paypal apparently does not check for complete addresses. Many times, I will have international customers who may not have entered a state/province. This puzzled me also, because there's no way you can do this if you use OsC because the input forms check for the entry. On the other hand, a Paypal Express Checkout can bypass all of this and use the customer's Paypal address to calculate the shipping through the OsC shipping modules. UPS shows an error because it cannot calculate the shipping without a state/province, whereas USPS does. I don't know about FedEx because I don't have the error checking turned on and sending me e-mails.
Anyway, the other issue is that the default shipping (set to lowest) is not my choice for some products. I guess I will edit the shopping_cart.php file to completely remove the "Check Out with Paypal" button on the shopping cart page. It is standard in OsC 2.3.4 and I wanted to use the complete features, but I guess this won't work unless I enable the shipping calculations on Paypal. I don't want to do that because their shipping only uses simple estimated rates per weight instead of directly interfacing with a shipping provider's rate server.
I hope that all makes sense and it helps someone.