I work for a company that offers bid management technology, but I'll try to give you some unbiased pointers:
1) You're right to go for an ASP solution because you want to buy the reliability and infrastructure behind a technology, as well as the technology itself.
2) Most technologies should be able to cope with Google, Yahoo, MSN and MIVA. But do your research - I can think of one big name system that had terrible problems integrating with the MSN API. Also understand how a technology provider is dealing with Google's fees and T&Cs for API access.
3) Forecasting is a difficult business with search - pulling traffic data from the SEs is not enough. You need something that can analyse your historical data to produce a forecast tailored for your campaign.
4) As well as rules-based systems, there are also portfolio algorithm-based systems. Again, do your research to understand the differences between the two so you can question the claims of technology providers.
I'm afraid I don't know anything about Indextools, so I can't help you there. But come back and ask more questions if you want to.