To clarify, sendmail is not a part of Perl , nor is it distributed with perl. It is a separate application. Your script just happened to be accessing the separate application. Any obsolescence in sendmail would come from itself, not from Perl. That said, a quick web search for "security concerns with sendmail" shows that many people consider sendmail insecure.

Rather than "accusing" your host, I would phrase it something like,

/usr/lib/sendmail used to exist on the server, but now it seems to not exist (in that, I cannot execute it at that path, and I cannot find it elsewhere). Was its remove a deliberate action, or an oversight during an upgrade? If it's deliberate, what alternatives do you support?

But before sending that message, I'd suggest looking for sendmail, and see whether it's really missing, or whether they just removed your permissions to execute it, or whether they moved it.

And really, the best solution, rather than pestering your host, would be to follow corion's advice