Description of problem: Although the sendmail is compiled with milter support, libmilter is not available as part of the sendmail package. There used to be a packaged called sendmail-devel, but it does not appear to be available for RHEL 3. Why would you compile in milter support in sendmail but not make the libmilter libraries available? Seems like a waste. You should compile milter out of sendmail or better yet, make libmilter and the headers available... perhaps something like the previously available sendmail- devel.
For now, just rebuild the sendmail SRPM and install sendmail-devel. That said, I have a bad feeling that if you do this, then the next sendmail errata update from Red Hat will not install due to dependency problems. Does Red Hat really expect us Enterprise customers to have to learn to live without anti-virus milters on their mail hubs?
sendmail-devel is now available in RHN