Did anyone ever fina a solution to this?
I had exactly the same problem.
My connection via my account in outlook was working fine both at home & work until about the same time.
Both came back meaningful outlook error (0x800CC0E) as the original poster suffered.

Vodafone call centre doesn't seem too clued up, the on-line FAQ doesn't hold much hope & I can't find my original instructions on how to set up vodafone.net.nz in outlook (either locally or on vodafone NZ)

Any help appreciated

Thanks