There may not be an idiomatic phrase with the exact same nuance (searching for something which is nearly impossible to find) which is native to Japanese. For your purposes, would it be acceptable to use the English idiom translated into Japanese?
If so, you could use something like:
藁の中から針を探す
wara no naka kara hari wo sagasu,
which basically means "searching for a needle among the straw".