I escalated the issue to the Telco and still no response. Just to be on the safe side i used a spare router (cisco 2811) with the exact same config and it worked perfectly (both in and out was succesfull)
I suspect a IOS bug or something related to the IOS. I tired the following IOS and still the same issue -
NB: (the IOS on the 2811 router is advancedenterprise -124-22.YB8)
I also see form the above debug that the router is sending a release complete signal as soon as the inbound call comes in.