What kind of data is not appropriate using CF to do recommendation?
The key is establishing a proper validation metric.

I notice you talk about how you tried different recommendation algorithms, but at the end of the day you evaluated them all with RMSE. But there's no particular reason to believe that minimizing RMSE generates a "subjectively better" recommendation experience for the user - it just happens to be convenient, and happens to work well in some industries, but there is no real reason why it must.

RMSE is measuring how well your recommender algorithm is predicting user behavior. But that's not the same as measuring recommendation quality. Maybe users value something else - familiarity, or serendipity, or some other quality of the item being recommended. Users don't really care about being predicted. 

Given your results, if you want to understand your users further, I'd focus my efforts in coming up with a mathematical metric that more closely matches the target you care about - user satisfaction - rather than RMSE. Once you know what metric you're trying to optimize, the algorithm to optimize it is much easier to select!