Huh, I thought it was Excel, but it was Shopify. When I download a CSV of the orders, it has munged the text already! Here's an example:

Bäckaströmsgatan

Jeez, that looks horrible! I'll have to contact support, because changing 20+ addresses on every order is no fun. This morning, I forgot to check, and printed almost thirty bucks in bad postage. Agh.