I would use 308/307 over 301/302.
Semantically, using a 303 redirect might be the most appropriate signal for what they are doing.
They could redirect to a specific result page if it's a clear, unambiguous match and they could redirect to a search results page if there are other possible matches.
301s are what you are supposed to do with things like changed URLs, so I cannot see it being a problem in this case. A 301 is nor duplicate content - it is one of the things Google likes you do do to avoid duplicate content.
It would probably be good to add a threshold to the similarity to prevent urls redirecting to something very different.