When you say this suddenly started I take it that you did no changes on your network that time?
That's right, I did not make any changes to my server and it just suddenly stopped working.
I don't have any other firewalls between the Mandrake machine and my DSL modem.
I tried the command tcpdump in my shell as root, and it says "command not found"
I did try typing "more /proc/net/ip_conntrack" whilst I made a remote computer attempt to connect, here's an excerpt
tcp 6 28 SYN_RECV src=126.96.36.199 dst=1XX.166.2XX.XX sport=34986 dport=80 src=1XX.166.2XX.XX dst=188.8.131.52 sport=80 dport=34986 use=1
I also tried configuring apache to listen on port 8000, instead of port 80, this worked perfectly...
I'm very much suspecting now that my ISP is blocking my OUTGOING responses to requests made on port 80 and port 21.