He construido un programa ELF de prueba utilizando el SDK de LSB (Tenga en cuenta que mi pregunta no es específica de LSB):

$ /opt/lsb/bin/lsbcc tst.c
$ ls -l a.out 
-rwxr-xr-x 1 math math 10791 2009-10-13 20:13 a.out
$ file a.out 
a.out: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.15, not stripped

Pero no puedo lanzarlo (si te aseguro el archivoes en el directorio ...):

$ ./a.out 
bash: ./a.out: No such file or directory

$ uname -a
Linux math 2.6.28-15-generic #52-Ubuntu SMP Wed Sep 9 10:48:52 UTC 2009 x86_64 GNU/Linux

Creo que hay una dependencia ELF que no se cumple, pero no sé cómo encontrarla. ¿Existe una herramienta similar a ldd para bibliotecas que se pueda usar para encontrar el enlace que falta?

No creo que esté relacionado con la diferencia 2.6.15 / 2.6.28-15 porque el compilador LSB está funcionando:

$ file /opt/lsb/bin/lsbcc 
/opt/lsb/bin/lsbcc: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.4, not stripped

Por si acaso, aquí está la sección dinámica ELF de a.out:

 0x0000000000000001 (NEEDED)             Shared library: [libpthread.so.0]
 0x0000000000000001 (NEEDED)             Shared library: [libm.so.6]
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
 0x000000000000000c (INIT)               0x400428
 0x000000000000000d (FINI)               0x400638
 0x0000000000000004 (HASH)               0x400278
 0x0000000000000005 (STRTAB)             0x400350
 0x0000000000000006 (SYMTAB)             0x4002a8
 0x000000000000000a (STRSZ)              121 (bytes)
 0x000000000000000b (SYMENT)             24 (bytes)
 0x0000000000000015 (DEBUG)              0x0
 0x0000000000000003 (PLTGOT)             0x600fe8
 0x0000000000000002 (PLTRELSZ)           24 (bytes)
 0x0000000000000014 (PLTREL)             RELA
 0x0000000000000017 (JMPREL)             0x400410
 0x0000000000000007 (RELA)               0x4003f8
 0x0000000000000008 (RELASZ)             24 (bytes)
 0x0000000000000009 (RELAENT)            24 (bytes)
 0x000000006ffffffe (VERNEED)            0x4003d8
 0x000000006fffffff (VERNEEDNUM)         1
 0x000000006ffffff0 (VERSYM)             0x4003ca
 0x0000000000000000 (NULL)               0x0