As I troll the many lists that I belong to I try to pick up recommendations on the best CF hosting companies.  I have currently used both advances.net and cjmgroup.com and I pulled the other list together from recommendations from CF-talk and the CFDev list.   Hopefully this gives you a good start on Coldfusion MX hosting.

http://www.advances.net
http://www.cjmgroup.com

From the CF-Talk List  & CFDev Lists

http://experthost.com
http://www.cfdynamics.com
http://www.nexpoint.net/
http://www.crystaltech.com/
http://www.hostmysite.com/
http://www.edgewebhosting.net/
http://www.media3.net/
http://www.cfhosting.ca/
http://www.w3media.net/