David,
You mentioned that you tried several metadata types.
Is it possible that this issue is related to FGDC metadata format? Perhaps the geoprocessing history is contained in the metadata, but is not currently viewable? Have you tried the option "FGDC CSDGM Metadata"?
Also, if the data is in a geodatabase, perhaps it may need to be upgraded? (One of my personal geodatabases gave me the following message - see attachment.)
Josh