The cost of adding and updating the indexes is actually a lot smaller than it's made out to be. Only under extreme change (meaning insert/update/delete) activity will you notice performance degradation from index updates. I think it would be safe to say that a vast majority of SQL Server databases don't fit into the "extreme" category.
For most businesses, the cost of adding the index is much less than the cost of re-developing a query/procedure. Especially when it's vendor supplied code and they have to pay for code changes 😉
Yes, in some cases a re-write is warranted, but why not give the end users some benefit straight away and put any re-writes on the work queue?
--------------------
Colt 45 - the original point and click interface 