A method, comprising: performing, by one or more computing devices of a network-accessible configuration discovery service; receiving, from a first data source, a first data set pertaining to one or more configuration items associated with a particular client; generating, based at least in part on analysis of the first data set, a service-side identifier for a particular configuration item associated with the particular client, wherein the first data set includes a data-source-side identifier of the particular configuration item, and wherein the first data set includes a first collection of one or more attributes of the particular configuration item; receiving, from a second data source, a second data set pertaining to one or more other configuration items associated with the particular client, wherein the second data set does not include the data-source-side identifier; determining that the second data set includes a second collection of one or more attributes of the particular configuration item, despite the second data set not including the data-source-side identifier, based at least in part on an analysis of the first collection and the second collection of the one or more attributes of the particular configuration item; updating, based at least in part on a first trust score associated with the first data source, and at least in part on a second trust score associated with the second data source, a first coalesced configuration record corresponding to the particular configuration item, wherein the first coalesced configuration record comprises the service-side identifier, the first collection and the second collection of attributes of the particular configuration item; and in response to a query received via a programmatic interface, transmitting a representation of at least a portion of the first coalesced configuration record. receiving, from a first data source, a first data set pertaining to one or more configuration items associated with a particular client; generating, based at least in part on analysis of the first data set, a service-side identifier for a particular configuration item associated with the particular client, wherein the first data set includes a data-source-side identifier of the particular configuration item, and wherein the first data set includes a first collection of one or more attributes of the particular configuration item; receiving, from a second data source, a second data set pertaining to one or more other configuration items associated with the particular client, wherein the second data set does not include the data-source-side identifier; determining that the second data set includes a second collection of one or more attributes of the particular configuration item, despite the second data set not including the data-source-side identifier, based at least in part on an analysis of the first collection and the second collection of the one or more attributes of the particular configuration item; updating, based at least in part on a first trust score associated with the first data source, and at least in part on a second trust score associated with the second data source, a first coalesced configuration record corresponding to the particular configuration item, wherein the first coalesced configuration record comprises the service-side identifier, the first collection and the second collection of attributes of the particular configuration item; and in response to a query received via a programmatic interface, transmitting a representation of at least a portion of the first coalesced configuration record.