**** UPDATE ****
I have now resolved this issue.
After a whole night of debugging I found the issue (and it seems to be a bug):

I am running Flash CS3 on my machine and I needed to install Flash 8 as well (due to some legacy Remoting project which I could not get to work in CS3). It seemed that my problems started at around that time - so I uninstalled Flash 8 and the RTMP connections work fine again.

MAC 9,0,115,0

RMTP Default Success 1.2s
RMTP Port 1935 Success 1.3s
RMTP Port 80 Success 1.1s
RMTP Port 443 Success 1.2s
RMTPT (Tunneling) Default Success 3.1s
RMTPT (Tunneling) Port 80 Success 3.1s
RMTPT (Tunneling) Port 443 Success 3s
RMTPT (Tunneling) Port 1935 Success 3s
**** END UPDATE ****

Original problem:
I'm having a problem with my iMac running Leopard (no, they are not perfect). A few days ago I noticed problems (long delays) connecting to standard RTMP addresses while RTMPT (tunneling) would still work fine. All other internet traffic also works fine.
At first I suspected that this was a router problem but testing the same connection from my laptop (running Tiger) worked fine, and I tested from within the same network which (I believe) eliminates both my network as well as the router as a cause for this problem.

I'm running the port tester on this page and this is the result I'm getting.

MAC 9,0,115,0

RMTP Default Success 60.9s
RMTP Port 1935 Success 61s
RMTP Port 80 Success 61s
RMTP Port 443 Success 61.1s
RMTPT (Tunneling) Default Success 2.8s
RMTPT (Tunneling) Port 80 Success 2.8s
RMTPT (Tunneling) Port 443 Success 2.7s
RMTPT (Tunneling) Port 1935 Success 2.9s

As you can see, the RTMP connection gets established eventually but it takes over a minute. A friend of mine ran the same test and he connected within 1 second, eliminating my FMS server as a source of the issue too (plus as mentioned I connected fine from my laptop).
I've reinstalled the latest Flash Player but the problem persists.

Can somebody suggests ways to troubleshoot this? I always connect eventually via RTMP but it takes over a minute most times...