Being in the hosting business myself I would recommend doing a bit of research. You will find that almost every single host on the market can host mambo. That is because all you need for mambo is PHP and MySQL.
I would recommend finding a host that is providing from the United States. I would then look for prospective hosts that you like and then try and contact them via a support ticket. If they don't reply within 24 hours I would move on.
Also you can check out;
www.webhostingtalk.com
Don't purchase hosting through their solicitation section. I would recommend looking at their reviews section. As stated above lunarpages.com is an excellent choice for uptime and security.
I can also highly recommend
http://hostrocket.com/ If you want a personal attention for your hosting solutions I would recommend someone from these forums. They will most likely be the most helpful when it comes to your hosting needs and mambo. Other hosting companies will not give you that personal touch.