Turns out the 3rd party DLL we are trying to add is an Excel add-in.
http://msdn.microsoft.com/en-us/library/ms165432(v=vs.90).aspx
In that article, MSFT states that "Not every component is a suitable candidate for registration-free COM. A component is not a suitable if any of the following are true:The component is intended for use as an add-in or a snap-in, for example an Office add-in or a control in a Web browser. Such components typically require some kind of registration scheme defined by the hosting environment that is beyond the scope of the manifest itself."
While we don't use the file along with Excel, I'm thinking that might be why it doesn't get recognized at runtime. We've asked the vendor for a compatible reg-free COM file. In the meantime we'll need to add that file to the prerequisites script. Not as encapsulated as I'd like.
Before I select this as an answer, I'd like to see if anyone else agrees that could be the issue.