Recently I ran into an issue with the SOAP adapter giving me the error 'Failed to Serialize the Message Part 'Foo'' ever so often. If I sent 20k messages through I was maybe getting about 100 messages suspended for this error. Now I spend about an hour looking at the messages that failed and I realized the problem really had 'nothing' to do with BizTalk and it was a serialization issue. I basically took the messages that failed and attempted to de-serialize them using a utility in .NET which is what the SOAP adapter is doing once the message is sent there. Needless to say I was getting the same message but this time I could see what field was causing the issue. It was a datetime type and it was blank.
So if your receiving this message please try to de-serialize the into a .NET type and see if you're getting the same error. There is something either missing or wrong about the data in your message. I just wish that the error message returning from BizTalk was a little more helpful here, like explaining what field is having the problem. Unfortunately I think that's a .NET issue and not a BizTalk one.