I have around 2000 customers in my store and more than half of them have badly formatted addresses (no capitalisation, whole address on one line, wrongly formatted post codes etc.).
When I ship I export the orders to a CSV file and then mailmerge to print labels. As part of this I format the addresses properly in Excel using the proper() function and an algorithm to format the post code. Splitting addresses from one line is done manually.
This is getting to be a bind so I wanted an easy way to do this and change the addresses in Magento. Going into each customer seperately is going to get very tedious!
How are you export order's addresses?
You probably will need modification to export function which will provide file with alredy formatted address.