I finally found a way to do this:

step 1: gdalwarp -dstnodata 0 -dstalpah -of GTiff foo1 foo2

This does two important things: it sets the destination No Data (outside border) values to 0, and it creates an alpha band.

step 2: gdal_polygonize.py foo2 -b 2 -f "ESRI Shapefile" foo3

The second step uses the alpha band (band 2), created in step 1, and creates a shapefile from that band.

This can then easily be scripted in a bash script, if you have many images, to create exact outlines for.

I finally found a way to do this:

step 1: gdalwarp -dstnodata 0 -dstalpha -of GTiff foo1 foo2

This does two important things: it sets the destination No Data (outside border) values to 0, and it creates an alpha band.

step 2: gdal_polygonize.py foo2 -b 2 -f "ESRI Shapefile" foo3

The second step uses the alpha band (band 2), created in step 1, and creates a shapefile from that band.

This can then easily be scripted in a bash script, if you have many images, to create exact outlines for.