A DVR, server, or other agent correlates media metadata from diverse sources, like an EPG data provider and multiple video-on-demand (VOD) service providers. Metadata sets from different sources are compared in order to attempt to identify identical programs to which the metadata sets pertain. From at least one metadata set, information about the program that the other metadata set lacks is selected. A “canonical” data structure instance for the program is created. The information that is lacking from at least one of the metadata sources is inserted into that instance. For each source from which a program is available, the DVR stores the identity of that source on the DVR's persistent storage device in association with the canonical data structure instance for that program. The DVR receives search criteria from a user and then searches the stored canonical data structure instance for programs that satisfy the criteria.