[exim] RFC's and DNS?

I am trying to explain to a company (and a very large one at that) that is
might be a good idea to provide DNS-entries for their mail handlers (that
are co-located at a not-so-big-and-pretty-clueless-co-loc-provider).

I get tons of "Bad HELO, host does not resolve" (Paraphrased of cource) in
my logs, and my fiancée can not mail me, and as she says "Tons of mail to
our customers comes back with the same error message, and our IT-department
is adamant in saying that it is not our problem".

So, is there in fact a good RFC here, or is not accepting mail from
non-resolving hosts a pretty bad idea?