Your value for maximum scale is too small. You've locked the maximum scaling so tight that AE needs to synthesize edges to fill the holes. Judging by the amount of cropping there's quite a bit of movement in your shot.
Increase the max scale value or try a different method of smoothness or a different stabilization amount. You could also try synthesize edges.
Youre indeed right about there being lots of movement, this is the start of a video with a small airplane darting off.
Your arguement that maximum scaling is too small doesnt seem to hold up to my problem though.
If I increase the maximum, the letterboxing gets even worse.
My goal is to get a steady shot of an aircraft in the air.
Tracking points dont seem to take hold of them, and warp stabilize also seems to get confused.
The only program that can do it flawlessly is deshaker in virtualdub.
How I wish I had that plugin for Premiere Pro.
Alas, still getting black barred and stabilization is atrociously bad.
I achieve the best results by pumping ungodly huge lossless avi files out of premiere,
then letting virtualdub do its thing for a day, then importing it back to premiere pro.
But its painstakingly slow and cumbersome and takes several terabytes.
Still, Its a bit unsettling that a free bit of software is making an expensive professional one look stupid.