There is a known issue with Quickbooks in which foreign addresses cannot be entered in the same way as standard US addresses. Due to this issue when a foreign address is entered correctly into All Orders, once it is sent to Quickbooks it will be formatted in Quickbooks incorrectly. Because of this the next time All Orders syncs with Quickbooks that incorrect format will come back over to All Orders.
There are a couple of solutions to this issue.
One is to enter the City/State/Zip Code/Country for the address in the Address 3 and Address 4 fields. Quickbooks will allow any values in those fields so no formatting should change. In addition, a custom version of any forms in the system which would have foreign addresses on them should be created. These custom forms should have the City/State/Zip/Country data fields removed so only Address 3 and Address 4 exist in case any data is accidentally entered into the City/State/Zip/Country fields which would make the formatting of the form incorrect.
Another solution is to open the company preferences and under the Advanced tab in the Quickbooks preference turn off the syncing of addresses from Quickbooks back into All Orders. This will prevent the messed up address from coming back over from Quickbooks and keep the correctly entered address intact in All Orders.