This is a gentoo server. There's a programme prog that can't execute. (Yes the execute permission is set)

About the file

$ ls
prog
$ ./prog
bash: ./prog: No such file or directory
$ file prog
prog: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), for GNU/Linux 2.2.5, dynamically linked (uses shared libs), not stripped
$ pwd
/usr/local/bin
$ /usr/local/bin/prog
bash: /usr/local/bin/prog: No such file or directory
$ less prog | head
ELF Header:
Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00 
Class:                             ELF32
Data:                              2's complement, little endian
Version:                           1 (current)
OS/ABI:                            UNIX - System V
ABI Version:                       0
Type:                              EXEC (Executable file)
Machine:                           Intel 80386
Version:                           0x1

I have a fancy less, to show that it's an actual executable, here's some more data:

$ xxd prog |head
0000000: 7f45 4c46 0101 0100 0000 0000 0000 0000  .ELF............
0000010: 0200 0300 0100 0000 c092 0408 3400 0000  ............4...
0000020: 0401 0a00 0000 0000 3400 2000 0700 2800  ........4. ...(.
0000030: 2600 2300 0600 0000 3400 0000 3480 0408  &.#.....4...4...
0000040: 3480 0408 e000 0000 e000 0000 0500 0000  4...............
0000050: 0400 0000 0300 0000 1401 0000 1481 0408  ................
0000060: 1481 0408 1300 0000 1300 0000 0400 0000  ................
0000070: 0100 0000 0100 0000 0000 0000 0080 0408  ................
0000080: 0080 0408 21f1 0500 21f1 0500 0500 0000  ....!...!.......
0000090: 0010 0000 0100 0000 40f1 0500 4081 0a08  ........@...@...

and

$ ls -l prog
-rwxrwxr-x 1 1000 devs 725706 Aug  6  2007 prog

$ ldd prog
      not a dynamic executable

$ strace ./prog
1249403877.639076 execve("./prog", ["./prog"], [/* 27 vars */]) = -1 ENOENT (No such file or directory)
1249403877.640645 dup(2)                = 3
1249403877.640875 fcntl(3, F_GETFL)     = 0x8002 (flags O_RDWR|O_LARGEFILE)
1249403877.641143 fstat(3, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 0), ...}) = 0
1249403877.641484 mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x2b3b8954a000
1249403877.641747 lseek(3, 0, SEEK_CUR) = -1 ESPIPE (Illegal seek)
1249403877.642045 write(3, "strace: exec: No such file or dir"..., 40strace: exec: No such file or directory
) = 40
1249403877.642324 close(3)              = 0
1249403877.642531 munmap(0x2b3b8954a000, 4096) = 0
1249403877.642735 exit_group(1)         = ?

About the server

FTR the server is a xen domU, and the programme is a closed source linux application. This VM is a copy of another VM that has the same root filesystem (including this programme), that works fine.

I've tried all the above as root and same problem.

Did I mention the root filesystem is mounted over NFS. However it's mounted 'defaults,nosuid', which should include execute. Also I am able to run many other programmes from that mounted drive

/proc/cpuinfo:

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 15
model   	: 4
model name  :                   Intel(R) Xeon(TM) CPU 3.00GHz
stepping    : 1
cpu MHz 	: 2992.692
cache size  : 1024 KB
fpu 	: yes
fpu_exception   : yes
cpuid level : 5
wp  	: yes
flags   	: fpu tsc msr pae mce cx8 apic mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm syscall nx lm constant_tsc pni monitor ds_cpl cid cx16 xtpr
bogmips : 5989.55
clflush size    : 64
cache_alignment : 128
address sizes   : 36 bits physical, 48 bits virtual
power management:

Example of a file that I can run

I can run other programmes on that mounted filesystem on that server. For example:

$ ls -l ls
-rwxr-xr-x 1 root root 105576 Jul 25 17:14 ls
$ file ls
ls: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), for GNU/Linux 2.6.9, dynamically linked (uses shared libs), stripped
$ ./ls
attr    	cat	   cut		  echo	      getfacl	ln	  more		 
... (you get the idea) ...
rmdir       sort       tty
$ less ls | head
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1