What you posted was the sendmail.mc file. That might not be the options your system was running on if you never actually ran it through the macro processor. As I was looking through the rest of the thread, it looks as if you are not running on the settings in the sendmail.mc file. Do you run webmin on this server, as it will allow you to make changes directly in your sendmail.cf file.
Yes, actually I do use Webmin to manage this server. I made that change you suggested in the webmin interface (sendmail.m4) and rebuilt it from there.
-R