We have a Sales Order where the Shipping Cost is 4000. When we convert the SO to Invoice, using the Bill button, the shipping cost of the Invoice is 16000. I'm looking all over. Any idea ?

Check the shipping cost item fulfilment

There's 6 IF, all with 0 Shipping Cost. Really strange

Thats strange. Try checking the shipping item if it is set to use a flat rate.

Curious -- Is the item on the SO marked "Shipped Individually" flag? Are there four skus or a QTY of four on the SO? I'm wondering if it's trying break the shipment into four shipments, hence multiplying the freight cost into four freight costs. Just a shot in the dark.