The public API function for address_book.accept_contact_invitation does not function correctly. I have been able to reproduce this bug on a number of different msn accounts. Here is the process to reproduce the bug.

Use the official msn client and login. Add to your contact list a test account that will login with pymsn. Make sure the the pymsn client is NOT connected first.

Login with pymsn and list the contact list. You should have something like:
<pymsn.Contact id='00000000-0000-0000-0000-000000000000' network='1' account='username@live.com' memberships='PENDING'>

This is the method that I use to accept pending invites:
    contacts_to_add = self.address_book.contacts.\
                search_by_memberships(pymsn.Membership.PENDING)
        for contact in contacts_to_add:
            self.address_book.accept_contact_invitation(contact)

The process goes like this in the debug:
SOAPAction: http://www.msn.com/webservices/AddressBook/ABContactAdd
(receive confirmation)
SOAPAction: http://www.msn.com/webservices/AddressBook/ABFindAll
(receive confirmation)
SOAPAction: http://www.msn.com/webservices/AddressBook/AddMember
<?xml version="1.0" encoding="utf-8"?>
<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/">
	<soap:Header>
		<ABApplicationHeader xmlns="http://www.msn.com/webservices/AddressBook">
			<ApplicationId xmlns="http://www.msn.com/webservices/AddressBook">996CDE1E-AA53-4477-B943-2BE802EA6166</ApplicationId>
			<IsMigration xmlns="http://www.msn.com/webservices/AddressBook">false</IsMigration>
			<PartnerScenario xmlns="http://www.msn.com/webservices/AddressBook">ContactMsgrAPI</PartnerScenario>
		</ABApplicationHeader>
		<ABAuthHeader xmlns="http://www.msn.com/webservices/AddressBook">
			<ManagedGroupRequest xmlns="http://www.msn.com/webservices/AddressBook">false</ManagedGroupRequest>
			<TicketToken xmlns="http://www.msn.com/webservices/AddressBook">t=9uPxLdgDtE5SGZPgeRF8KIKou5m6hag!xfhtVfHPpVq2GkeJDBsVWijnzDKsVxYD8kjHhzxsORmv9e*54AizmQFCgVqQ7Q58hEFIg5vNOfzUK22WerKI0!9uO!TUl9G*hTjTz0GzTFf1DF0RIJ04Yxlg$$&amp;p=9DTsVrLJfF77g9!fMIyxrr7jmDflD15PGKrGdg1RHjrRWQlVBdC6QL8id4Vxmb2eLyHb3qrgMIz8onOoWq6VmqQMPercR6vYMZMdkO9WebBkMXbplDrdklpOubEJAeBT*N2ZRkf*0JuVe9BgNNTMI9SCW6Qj9ek5MxW20J3Vd!k1B8SByTUVNN!e1EBizUaQVT</TicketToken>
		</ABAuthHeader>
	</soap:Header>
	<soap:Body>
		<AddMember xmlns="http://www.msn.com/webservices/AddressBook">
			<serviceHandle>
				<Id>0</Id>
				<Type>Messenger</Type>
				<ForeignId/>
			</serviceHandle>
			<memberships>
				<Membership>
					<MemberRole>Reverse</MemberRole>
					<Members>
						<Member xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:type="PassportMember">
							<Type>Passport</Type>
							<State>Accepted</State>
							<PassportName>username@live.com</PassportName>
						</Member>
					</Members>
				</Membership>
			</memberships>
		</AddMember>
	</soap:Body>
</soap:Envelope>
(FAIL)
<?xml version="1.0" encoding="utf-8"?>
<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>
		<soap:Fault>
			<faultcode>soap:Client</faultcode>
			<faultstring>Member already exists </faultstring>
			<faultactor>http://www.msn.com/webservices/AddressBook/AddMember</faultactor>
			<detail>
				<errorcode xmlns="http://www.msn.com/webservices/AddressBook">MemberAlreadyExists</errorcode>
				<errorstring xmlns="http://www.msn.com/webservices/AddressBook">Member already exists </errorstring>
				<machineName xmlns="http://www.msn.com/webservices/AddressBook">BAYABCHWBB144</machineName>
				<additionalDetails>
					<originalExceptionErrorMessage>BY2ABCHSQLA132.ABCHA1320230..prc_ABRoleMappingAddInt_W12R1:  Member Already Exists in specified Role(s) RoleMap Add failed - II
BY2ABCHSQLA132.ABCHA1320230..prc_ABRoleMappingAdd_W12R1:  Failed to execute stored procedure prc_ABRoleMappingAddInt.</originalExceptionErrorMessage>
				</additionalDetails>
			</detail>
		</soap:Fault>
	</soap:Body>
</soap:Envelope>


I traced the issue down to the UpdateMembershipsScenario. It seems like the UpdateMembershipsScenario is trying to add the member to the 'REVERSE' list? This doesn't seem to make sense. 

Oddly enough if you logout (quit pymsn client) and start up again the contact will be properly added to the addressbook. I think what needs to happen is UpdateMembershipsScenario should run a sync() rather than the additional add call.