I tried with Deshaker 3.0 but couldn't get it to work. I then stabilized it using an old version of Mercalli that is built into Vegas. I didn't play around with the settings much, so I assume that some of the funkiness in the clouds and around the edges of the video could be improved. Also, my Mercalli is almost a decade old and their newer versions are far better. It is expensive, but is probably the best stabilizer out there. You can download the trial and see if it is worth the (considerable) expense to purchase.
Here's a link to the result (which I down res'd to HD just to make it easier to deal with).
Stabilized Video