"Is it common to see hosting companies that say they offer perl and then not deliver on their promise? I mean that's the only reason I chose these hosts, because they included perl in the list."

I've not looked in a long time, not since it's become cost effective to spin up my own server and deal with everything myself. Look at companies like Scaleway, Digital Ocean (update: or pair). Some of the low tier hosts advertise Perl, meaning they have an interpreter installed on the machine, others offer better perl support (sometimes via cpannel or similar). As far as managed services go, you tend to get what you pay for.