I had once inquired MTNL and promised to provide all relevant docs of rented address, still they denied. But then its an year back story. May be they would have changed their policy.
Either you did not do your homework well or might have come across a useless MTNL sarkari babu. In the first place, there is no such policy in MTNL not to give connection on rented premises. What do you think? How many people in a city of Crore plus are living in their own homes? How many offices are owned? There are lacs of MTNL connections on rented premises.
You just needed to be more persistent and demanded it through the right medium. That you can do now also and get MTNL. Go and meet some Senior Officer in the exchange where you will be submitting the connection application.