IExtensibleDataObject usage in clients

that is incorrect usage of IExtensibleDataObject. You have modified data contract on the server side an you have marked new field as required so it means you have broken versioning and nothing helps you.

IExtensibleDataObject is for other purpose. Let assume that you have modified your client so that data contract on the client contains MiddleName. Now you set the MiddleName and use Add service operation. What value of MiddleName will be in returned Employee object? If you don't use IExtensibleDataObject the value will be null, if you use IExtensibleDataObject the value will be same as you set to input parameter.

When using DataContractSerializer WCF throws away all non understood parameters. IExtensibleDataObject avoid this by storing all those parameters in special collection and sending them back to client.

If you want to use contract versioning forget about required fields. That is the first thing which will break it.

I'm afraid that's not the correct usage of IExtensibleDataObject, the IExtensibleDataObject interface is designed to support version round-tripping, have a read of this MSDN article on forward compatibility:

http://msdn.microsoft.com/en-us/library/ms731083.aspx

And here's another article on best practices on Data Contract versioning in general: http://msdn.microsoft.com/en-us/library/ms733832.aspx