gdal - Merge overlapping DEMs with irregular boundaries

I have a 10m DEM covering part of a state, a 20m DEM covering the whole state, and a 90m DEM covering the whole country. How can I merge them together, getting the best quality available in each area?

The 10m and 20m are provided in ADF format, but I've converted them to .tif using ogr2ogr.

Using gdal_merge doesn't work, because the boundaries of each area are irregular. This is the result:

(The northeastern edge of the state is irregular, but there obviously shouldn't be the gap in the middle.)

UPDATE If it's useful, I also have a shapefile for each 10m DEM, marking its extent.

UPDATE 2

Ok, here's what the whole state looks like with the 20m DEM.

The process I'm going through so far is this:

for f in dtm20m dtm10m_nw dtm10m_e; do
export GDAL_CACHEMAX=1000
echo -n "Re-projecting: "
gdalwarp  -s_srs EPSG:3111 -t_srs EPSG:3785 -r bilinear ./vmelev_${f}/${f} ${f}-3785.tif 

echo -n "Generating hill shading: "
gdaldem hillshade -z 5 $f-3785.tif $f-3785-hs.tif
echo and overviews:
gdaladdo -r average $f-3785-hs.tif 2 4 8 16


done