Exporting primary addresses exports non-primary addresses for some contacts
It turns out that the "Search Primary Details Only" setting causes this problem (found under Administer-> Customize Data and Screens-> Search Preferences). It seems that if this setting is off, the listings and export will default to the address which was created earlier.

See here for details: 
Contact Search Results Address Type

This is a weird behaviour in the listings, but for the exports seems like a bug as selecting primary address types in an export does not return primary addresses.