Ludwig,
For our t-shirt site, thoughtcrimeink.com, I had to abandon a complex shipping formula for something really basic. There is a basic shipping charge, and if you’re not logged in or logged in as an “international” customer, the site has an ever-present button that reminds you to add an extra charge before shipping. This is processed as a PayPal “donation” since Paypal (frustratingly) doesn’t actually do complex shipping calculations. Simplifying worked for us however, as we’re in the apparel industry, and t-shirt shipping seems to be going in the flat-shipping direction. 90% of our customers don’t screw up, so the ever present button works.
However, if you have to do complex shipping, you might want to search these forums (or Google) for xClick Cart. I found out about it yesterday and am definitely going to be experimenting with it for our site, since we are looking to add coupons. It’s a server-side PayPal clone that acts like PayPal, but is an intermediary where you can set up shipping calculations, coupons, etc.—and when the buyer is done the contents of the cart and its transactions are sent to PayPal as a single “item.” Someone’s also written a tutorial on integrating it with ExpressionEngine (Google that too).
Hope this helps! Good luck!