I've fixed it, or at least worked around it in a way that seems to solve all of our issues. When I added PDF icon support to our server, I used the following XML in the C:\Program Files\Common Files\Microsoft Shared\Web Server Extensions\12\TEMPLATE\XML\DOCICON.XML file, as suggested in the linked KB article:
<Mapping Key="pdf" Value="pdficon.gif" />
But this document also specifies an OpenControl attribute for many file types, and when it appears it's either empty, or contains "SharePoint.OpenDocuments":
<Mapping Key="docx" Value="icdocx.gif" EditText="Microsoft Office Word"
OpenControl="SharePoint.OpenDocuments"/>
or:
<Mapping Key="chm" Value="icchm.gif" OpenControl=""/>
As it turns out, that OpenControl attribute is what governs how the browser is told to open the document; either using the SharePoint.OpenDocuments IE add-on, or using the browser's default handler for that type if the attribute is blank.
The key in this case is that if the attribute is missing, SharePoint defaults to telling the browser to use the add-on, which displays the warning message. Simply changing that element in our file to
<Mapping Key="pdf" Value="pdficon.gif" OpenControl="" />
and recycling the application pool fixed the problem for us. All of our documents are either PDFs or Office docs, and the add-on doesn't show the warning message for Office docs as long as the SharePoint site is in the user's Trusted Sites zone.