The increase in the penetration of wind in the current energy mix is hindered by its high volatility and poor predictability. These shortcomings lead to energy loss and increased deployment of fast-ramping generators. The use of energy storage compensates to some extent these negative effects; it plays a buffer role between demand and production. We revisit a model of storage proposed by Bejan, Gibbens and Kelly. We study the impact on the performance of energy conversion efficiency and of wind prediction quality. We first provide theoretical bounds on the trade-off between energy loss and fast-ramping generation. For a large storage capacity, we show that this bound is tight and develop an algorithm that computes the optimal scheduling policy. Second, we develop two new scheduling strategies. We evaluate these policies on real data from the UK grid and show that they outperform existing heuristics. In addition, we give a rule-of-thumb for computing optimal storage characteristics for a given penetration of wind in the energy mix.