In Windows Mobile, I would recommend htc S710 pro. I am having this phone since the last two months and am extremely satisfied with it. Good email client. Internet Explorer Mobile is sufficient though not as good as a Symbian browser. You can always have Opera Mini also installed. I use browsing on the phone now more than browsing on the laptop.
It has btv2.0, EDGE, 2.0MP cam is decent enough, normal keypad as well as sliding QWERTY keyboard, and most of all, every feature of this phone can be used in India. Doesn't have 3G or dual cam or other features that you won't be using in an N73 or N82. And it has Wi-Fi too. With power saver mode it completely rocks.
And costs only 14k. Buy a 1GB microSD card for Rs.550 Kingston 5 yr warranty. And there you go. I don't have any idea about recording calls, but googling you should find one.
Best of Luck!!!