I think this challenge can be approached using string collection variables. It's tough to describe an imagined Flow, but I think it'd go something like this:
Fast Lookup for Custom Metadata Records
--> Loop over Custom Metadata Records
-----> For each record, add its key values (City, State, ZIP) to individual collection variables - i.e., one collection variable per data point you want to compare.
Source your Contacts (could be a Fast Lookup)
--> Loop over Contacts
-----> For each Contact, make a Decision
--------> If each key data point collection variable (City, State, ZIP) contains the
value present on this Contact, update the data on this Contact as desired.
Perform a Fast Update of your Contact list.
I don't think you'll be able to approach it as comparing a list of addresses to a list of addresses; Flow doesn't have Address as an first-class type. You could do that in Apex with a Set of a custom class that implements hashCode()
(although it wouldn't be an especially natural idiom there either).
Breaking it down into specific data points and ANDing criteria (listOfCities CONTAINS contactsCity AND listOfZIPs CONTAINS contactsZip AND...
) is going to fit the bill for this application.
contains
operator supports checking collection contents if you have a collection of primitive values (i.e., strings).