Replacing a material found on many objects to another material at once for all of those objects. Possible?
Yes

If you bring up the select linked menu (Shift-L) with one object that have the material of interest and then choose Material, then use the link menu (Ctrl-L) you can link material from the active object (last selected).