Just FYI I tried on Quicksilver and everything works fine

{
   "Id":504,
   "Created":"2018-06-08T12:42:15.97Z",
   "Currency":"USD",
   "CustomerId":"b6606261-7a31-4556-adf1-141dde2e4744",
   "Forms":[
      {
         "OrderFormId":-1,
         "Name":"Default",
         "Shipments":[
            {
               "ShipmentId":-1,
               "ShippingMethodId":"515056e2-b696-4281-92e1-93d09f504bb8",
               "ShippingAddress":{
                  "Id":"No addresses exists",
                  "FirstName":"Quan",
                  "LastName":"Mai",
                  "Line1":"abcxyz",
                  "City":"STOCKHOLM",
                  "CountryCode":"SWE",
                  "CountryName":"Sweden",
                  "PostalCode":"111 56",
                  "RegionCode":"Alabama",
                  "RegionName":"Alabama",
                  "Email":"vimvq1987@gmail.com",
                  "Properties":{

                  }
               },
               "OrderShipmentStatus":1,
               "WarehouseCode":"stockholmstore",
               "LineItems":[
                  {
                     "LineItemId":-1,
                     "Code":"SKU-44477844",
                     "DisplayName":"Puma Guida Moc SF Chase Mens Size 14 Red Leather Loafers Shoes UK   EU 48.5",
                     "PlacedPrice":52.500000000,
                     "Quantity":1.0,
                     "InventoryTrackingStatus":1,
                     "Properties":{

                     },
                     "InStockQuantity":451.0,
                     "InventoryStatus":1,
                     "MaxQuantity":100.000000000,
                     "MinQuantity":1.000000000,
                     "TaxCategoryId":1,
                     "IsSalesTaxUpToDate":true
                  }
               ],
               "Properties":{

               },
               "IsShippingCostUpToDate":true,
               "IsShippingTaxUpToDate":true,
               "ShippingCost":20.000000000,
               "OperationKeys":{

               }
            }
         ],
         "Promotions":[

         ],
         "CouponCodes":[

         ],
         "Payments":[
            {
               "CardType":"Credit card",
               "CreditCardNumber":"4662519843660534",
               "CreditCardSecurityCode":"212",
               "ExpirationMonth":6,
               "ExpirationYear":2018,
               "Amount":72.5000000000,
               "BillingAddress":{
                  "Id":"Billing address (ab5)",
                  "FirstName":"Van",
                  "LastName":"Mai",
                  "Line1":"Ab5",
                  "City":"Bandhagen",
                  "CountryCode":"SWE",
                  "CountryName":"Sweden",
                  "PostalCode":"12476",
                  "RegionCode":"Alabama",
                  "RegionName":"Alabama",
                  "Email":"vimvq1987@gmail.com",
                  "Properties":{

                  }
               },
               "CustomerName":"abc",
               "ImplementationClass":"EPiServer.Commerce.Order.Internal.SerializableCreditCardPayment, EPiServer.Business.Commerce, Version=12.3.1.0, Culture=neutral, PublicKeyToken=8fe83dea738b45b7",
               "PaymentMethodId":"87080c43-d08d-4471-a4fd-9897e2530358",
               "PaymentMethodName":"GenericCreditCard",
               "Status":"Pending",
               "TransactionType":"Authorization",
               "Properties":{

               }
            }
         ],
         "Properties":{

         }
      }
   ],
   "MarketId":"US",
   "MarketName":"USA",
   "Modified":"2018-06-08T12:42:38.687617Z",
   "Name":"Default",
   "Notes":[

   ],
   "OrderLink":{
      "OrderGroupId":504,
      "Name":"Default",
      "CustomerId":"b6606261-7a31-4556-adf1-141dde2e4744",
      "OrderType":"EPiServer.Commerce.Order.Internal.SerializableCart, EPiServer.Business.Commerce, Version=12.3.1.0, Culture=neutral, PublicKeyToken=8fe83dea738b45b7"
   },
   "OrderStatus":4,
   "Properties":{

   },
   "IsTaxTotalUpToDate":true
}

And the order has correct billing address ... 

Thanks Quan,

Any pointer to how I can find the error?

Can you post your entire code for creating the order here? from loading the cart? 

A difference I spot is that the adress on the Shipment is missing in your cart data, maybe the SaveAsPurchasOrder takes it's OrderAdress data from the Shipment and not the Payment?

Maybe due to them being named the same thing? "Invoice". Try renaming the shipping adress.

I doubt it. It should take both into account. Well it's not possible that we might have missed something, but it's very unlikely 

Yikes, you're fast! :D

I've edited my answer with a possible reason. :P

Yes that is a very good guess. I missed that. When you save the addresses they are identified by names so matching names can be the problem 

Nice works guys, 

If I choose a differnt shipping address it works.

I try the reuse addresses link explained here: https://world.episerver.com/documentation/developer-guides/commerce/orders/order-manipulation/ (Working with addresses)

var orderRepository = ServiceLocator.Current.GetInstance<IOrderRepository>();
var orderGroupFactory = ServiceLocator.Current.GetInstance<IOrderGroupFactory>();
var contactId = PrincipalInfo.CurrentPrincipal.GetContactId();
var cart = orderRepository.LoadCart<ICart>(contactId, "Default");

var address = orderGroupFactory.CreateOrderAddress(cart);

//Use Id to reuse
address.Id = "Billing";
cart.GetFirstForm().Payments.First().BillingAddress = address;

//Since there is already an address with "Billing" it will use that address instead of creating another one on the order.
var reuseOtherAddress = orderGroupFactory.CreateOrderAddress(cart);
reuseOtherAddress.Id = "Billing";
cart.GetFirstShipment().ShippingAddress = reuseOtherAddress;