Newline characters disappearing

Question

The issue that I am having is that when I download email messages from a Microsoft outlook webmail account, sometimes newline characters are disappearing, resulting in onelongunbrokenline. But only sometimes. Here is the example I am dealing with right now:

Original body of message being downloaded from Microsoft Outlook Web App (dollar signs included because I have :set list on in vim):

Gobble$
This is a message with$
Multiple lines$
$
Hello$

Body of message that I actually end up receiving (also has :set list on in vim):

GobbleThis is a message withMultiple lines^M$
Hello ^I^I ^I ^I^I =^M$

There are clearly a few other things going on here which I also don't understand - where are the tab (^I) characters coming from? Where is that equals sign coming from?

Here is the code that does the downloading (using the python library IMAPClient):

## Connect, login and select the INBOX
server = IMAPClient(HOST, use_uid=True, ssl=ssl)
server.login(USERNAME, PASSWORD)
select_info = server.select_folder('INBOX')

#Get messages since a certain time:
message_list = server.search(['SINCE %s' % cutoff.strftime('%d-%b-%Y')])
response = server.fetch(message_list, ['RFC822'])

for msgid, data in response.iteritems(): 
    msg_string = data['RFC822'].__str__()
    msg = email.message_from_string(msg_string)
    payload = msg.get_payload()
    body = payload
    print body