Not true - if mark has a resume listing a successful employment post-cookie incident I would call them for a reference. A good reference isn't completely trustworthy but 2 or 3 of them with good companies and I'd be convinced.
The HR pipeline treats any sort of checkered pass as and immediate rejection, whether or not a hiring manager would treat it as such
To combat this prejudice I would fully expect to have to lower my expectations in the form of lower wage or other restriction. If I offer to work for half the normal pay not only will I definitely get hired but I'll get a good reference providing I prove myself capable and trustworthy.
You're coming at this from a viewpoint that implies that companies want to help people, when we are already dealing with that fact that they absolutely do not