> It's really not hard to imagine that the search for alien life is a problem of asking a question for a rare/over-specified solution.

Life is quite messy and obvious. It seems quite likely that traces would exist.