The Soap message that is transfered from the client to server actually has all the required SOAP headers. I was retrieving the message at the wrong place.
The runtime executes in the following order :
1) Creating the SOAP message from the proxy object.
2) Executing the SOAP extension if one exists.
3) Runs the WSE filters on the SOAP message to add the required headers depending on the objects present in SoapContext.
Since I was looking at the soap message from the second step, the header were not added.
The correct method to retrive SOAP message is using the WSE settings tool.
1) Right click on the project and select "WSE Settings"
2) Select the Diagnostics tabs and check "Enable Message Tracing". The 'input file' and 'output file' has the final SOAP Request and SOAP Response messages.