Budget? It is imperative that you give a budget else people will suggest models that might exceed the amount you wish to spend.
A general guide is to look for GPRS Class 10. Currently, it is the highest class and that means the best GPRS phones will be those with Class 10. I don't know if Airtel Mobile Office supports EDGE; but if it does, then get a Class 10 phone with EDGE. That should be a good combo