Here are some suggestions, which I cannot guarantee will work since I haven't tried:
1. Create a custom class EmployeeEntry which contains the key and the associated instance of Employee.
Have your web service method accept an array of EmployeeEntry instances:
2. Create a custom class that wraps the collection.
Then in your web service method, you take an instance of the wrapper class as parameter:
Personally, I would try to go for alternative one.