High scalability is somewhat subjective, and often not that interesting. It's relatively easy to design an inefficient solution and "scale" it by throwing more machines at it. It's hard to reduce the footprint of something that's big and/or slow.
The hardest problem I've bumped into is getting the model right for making something distributed at all.