Linux: execution of a program fails with permission denied, but the file has r_xr_xr_x mode

You have an executeable; all modes are ok (eg r_xr_xr_x), but if you try to run the program, you get an "permission denied"-error.
AFAIK there are two possible reasons for this:
First, you try to start an old libc5-executeable on an libc6-machine without compat-libs.
Solution: install the libc5-compat-libs that comes with your distribution and hope that they work.
Second, maybe you try to start the executeable from a mount point that has not set the exec-Flag (the location of the executeable, NOT the current working directory). Take a look at /etc/fstab, if you see a line like
/dev/scd0 /cdrom iso9660 ro,user,noauto 0 0,
than you can see that the exec flag is not set.
Solution: change the line to
/dev/scd0 /cdrom iso9660 ro,user,noauto,exec 0 0,
then the "permission denied"-error will disappear.