Right, so if the first part is what's delaying the output, then I might be doing the wrong thing by concentrating on fine-tuning "my.cnf".
After upgrading to 2GB I just bumped the "key_buffer" to 256M (and the "table_cache" to 512). Not sure what I need exactly but I have around 700 users simultaneously at peak time and a rather large database to deal with.
Funny think is that the CPU shouldn't really be overworked as it's a Dual Xeon and in the stats it seems like it's plain sailing all the way. The drive isn't SCSI or even SATA, maybe that's the issue. But some of these delays are coming when the number of people online is about 150 and not 700. Very strange...