The Yahoo Music dataset has these characteristics (more items than users), and a combination of methods (including the SGD-based matrix factorization that people call "SVD" in recommender lore) did pretty well on it (KDD Cup 2011: http://kddcup.yahoo.com/).
What I find a little disappointing is that the top 3 prizes for this Netflix-Prize-style competition total $7,000 in value. Is technical brainpower, even that of students, really worth that little? Maybe startups should band together to hold their own optimization contests if the 'market rates' are so low.
