Thanks to all those that helped!
Here is a very basic example to talk to exchange. Be aware that you also have to patch the Services.wsdl file to include these lines:
Put these lines at the bottom of Services.wsdl before the closing </wsdl:definitions>:
<wsdl:service name="ExchangeWebService">
<wsdl:port name="ExchangeWebPort" binding="tns:ExchangeServiceBinding">
<soap:address location="https://mail.gemini.edu/EWS/Exchange.asmx"></soap:address>
</wsdl:port>
</wsdl:service>
The first xml definition and attr = c.service.CreateItem(__inject={'msg':xml}) call will generate an email.
The second xml definition and attr = c.service.ResolveNames(__inject={'msg':t}) will perform a user lookup
import suds
from suds.client import Client
from suds.transport.https import WindowsHttpAuthenticated
import logging
logging.basicConfig(level=logging.INFO)
logging.getLogger('suds.client').setLevel(logging.DEBUG)
url = "file:///path/to/Services.wsdl"
user = 'DOMAIN\user'
password = "pass"
ntlm = WindowsHttpAuthenticated(username=user,password=password)
c = Client(url, transport=ntlm)
xml = '''
<soap:Envelope xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema">
<soap:Body>
<CreateItem MessageDisposition="SendAndSaveCopy" xmlns="http://schemas.microsoft.com/exchange/services/2006/messages">
<SavedItemFolderId>
<DistinguishedFolderId Id="sentitems" xmlns="http://schemas.microsoft.com/exchange/services/2006/types"/>
</SavedItemFolderId>
<Items>
<Message xmlns="http://schemas.microsoft.com/exchange/services/2006/types">
<ItemClass>IPM.Note</ItemClass>
<Subject>Sent via Python->Exchange->EWS</Subject>
<Body BodyType="Text">This message has been sent to you via Python, Exchange and EWS :)</Body>
<ToRecipients>
<Mailbox>
<EmailAddress>jeckersley@gemini.edu</EmailAddress>
</Mailbox>
</ToRecipients>
</Message>
</Items>
</CreateItem>
</soap:Body></soap:Envelope>'''
#attr = c.service.CreateItem(__inject={'msg':xml})
xml = '''
<soap:Envelope xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/" xmlns:t="http://schemas.microsoft.com/exchange/services/2006/types">
<soap:Body>
<ResolveNames xmlns="http://schemas.microsoft.com/exchange/services/2006/messages" xmlns:t="http://schemas.microsoft.com/exchange/services/2006/types" ReturnFullContactData="true">
<UnresolvedEntry>jeckersley</UnresolvedEntry>
</ResolveNames>
</soap:Body>
</soap:Envelope>
'''
attr = c.service.ResolveNames(__inject={'msg':t})
print attr