We had this problem too. We use Paypal Express 3.1 and osc 2.3.3.4.
At the beginning Paypal worked well, shipping have been calculated correctly. From one day to the other, shipping method was always set to free pick up in store.
In the checkout_confirmation and at the paypal side, the correct shipping method and the correct shipping cost were displayed. However, the wrong shipping method and the false shipping cost were sent to the customer and were stored into our db.
With the reference of the thread
http://www.oscommerce.com/forums/topic/398267-paypal-express-31-update-not-pushing-shipping-method-selected/
to the instant notification function and the descriptions in the manual of the contribution I have found the cause of the error. Many thanks to Kevin for his hint.
The cause is the missing 'Payment Zone' for Paypal.
Goto 'Locations / Taxes' -> 'Tax Zones' in the admin menu. Then create a tax zone for the countries from which you want to accept the paypal payments, for example 'worldwide'. I used the contribution "Rest of the World tax zone". (Contrib "Rest of the World tax zone" from 21.Jul 2014 contains an error and does not work. Change line45 to: <?php echo tep_draw_form('doprocess', 'setup_international_zone.php', 'action=' . $_SERVER['PHP_SELF'], 'post'); ?> and it works fine).
You can also manually create the new tax zone or perhaps there is already an appropriate zone.
If the new zone has been created, then go to 'Modul' -> 'Payment' -> 'PayPal Express Checkout'. Scroll down to 'Payment Zone' and select 'worldwide' (or the name you've chossed) from the pull-down menu. The default '--none--' does not work and causes the described incorrect behaviour. Click Save and afterwards enjoy the working 'PayPal Express Checkout'.