The first suggestion on improving the selection of a COTS product is the same as any internally developed application, namely a better understanding of the goals of the project. While your stakeholders feel that they could see labor and customer satisfaction increases with a new system, it wasn't clear (intentionally) from the description that the stakeholders wanted a COTS package, only that the CIO preferred one. Was there a bias on the part of the CIO towards using a COTS package or did she think it just made more financial sense to go that direction? Asking additional questions during the initial discussion with the CIO would have been a good first step.
Next, why was a list of current system functionality given to the vendors? The CIO made no mention of wanting to try and replicate the existing system in a COTS package. If the users main complaint is speed and older technology, could the existing system have been enhanced to meet those needs quickly? The stakeholders did not say they were unhappy with the system as a whole, just those two aspects of it.
But a more fundamental question is what do the stakeholders need? If the existing functionality works for them, with the requested speed improvements, then it doesn't sound as if they were necessarily unhappy with what the current system. If speed and old technology were ways users were expressing their displeasure with a product that was in reality more deeply flawed, only a rigorous review of the business processes in comparison with the system processes will find the underlying problem.
At its core, not enough questions were asked. The price tag returned by the COTS vendors were set very high as recreating an unknown system on top of their product is not usually cheap. Such a high price tag is a method vendors use, and rightly so, to provide incentive for clients to reassess their request and frame the conversation in terms of actual needs and not just a functionality list.
What other thoughts do you have on this situation? Have you been in a similar place yourself? Let us know what you did in the comments.