Varnish gives you your own throttle for how often you want invalidation. It's a tool specifically designed to make misbehaving apps -- i.e., that widget -- misbehave. You just have to slap the dog on the nose when it behaves. I'm just saying you could have made this work on Linode (and I have), but I do see your post-purchase rationalization at work, so I know anything I say will be fruitless anyway.
There's also the possibility that you had shitty neighbors.
There's also the possibility that you had shitty neighbors.