I have a material that belongs to some objects, but I can't find those objects. Is there a way to search for objects that have been assigned a certain material?
Yes. What you can do is use the Search engine tool in the Outliner. Since various aspects of each object's Object Data (including materials) are listed in the Outliner, the Search engine tool will turn them up as results. Note that you may have to MW scroll to bring the search bar into view.