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.