Wow, a range of proposals and attacks from various angles...where to begin...
I like letmebefell's suggestion of a five-year sunset provision, but if you will recall a little housing policy history, Ronald Reagan (and I am no defender of that administrations' record overall) did try to abolish the home-interest mortgage deduction in 1986, but it was retained at the last minute due to overwhelming lobbying pressure from realtors. So if Congress in its tax-reform frenzy could not accomplish it then, I very much doubt the current housing market could withstand another financial blow now.
The HMID is really a massive transfer of wealth to homeowners, and very wealthy ones in some cases at that. But it is the still the federal government's single largest housing subsidy.
I think Arlington's idea is too complicated to implement. Plus, what happens in the current market, where home values are dropping in some regions? These declines would distort the amount allowed for deduction relative to the fair-market value of the home, thereby incentivizing bad investment decisions (ie. logically, it would encourage buyers to get in at the apex of the market, when deductible levels are highest as a percentage of the fair market value of the home).
A version of run75441's proposal to "set a median deduction for various regions, states, or cities" already exists in the Fannie Mae conforming loan limit, which is calculated based on area median income (I think). Maybe.