How to know that your machine learning problem is hopeless?

You are right that this is a question of forecastability. There have been a few articles on forecastability in the IIF's practitioner-oriented journal Foresight. The problem is that forecastability is already hard to assess in "simple" cases. Suppose you have a time series like this but don't speak German: How would you model the large peak in April, and how would you include this information in any forecasts? Unless you knew that this time series is the sales of eggs in a Swiss supermarket chain, which peaks right before western calendar Easter, you would not have a chance.