The docs for HTML::Tidy say:

[HTML::Tidy is] meant as a replacement for HTML::Lint. If you're currently an HTML::Lint user looking to migrate, see the section "Converting from HTML::Lint"

So HTML::Lint isn't deprecated yet... but it sounds like it's heading that way.

And as they're both owned by the same author, I'm inclined to believe him :-)