I do a fair bit of training and have to say that I seem to concentrate most of my time teaching PM skills rather than demonstrating the tool. You cant show people how to perform EVM if they dont know what EVM is. 😉
I would suggest looking for a company that "gets Project Management" and knows the Toolset very well. That way they will look to tailor the training to what the organisation is looking to achive and use the training as a process to mature the PMO not just a technical dump