VirtualDub Deshaker performed miracles on a video I shot on a roller coaster with a point-and-shoot camera (no image stabilisation).
As pbristow said, download the latest version, and read the guide...
http://www.guthspot.se/video/deshaker.htm
...and read the guide again. Did I mention that you should read the guide?
Cheers,
David.