The last time this happened was over the past weekend. The thing that was different about this incident was that it happened despite a very strong password that should have made it essentially impossible for anyone to get access to the FTP account.

I sent the hosting service a support request, asking for a copy of the FTP log and any other assistance or advice they could provide.

I got the log, which showed no FTP access to the modified file during the period when the breach occurred.
Apart from ftp access, is there any other way to access that machine? SSH/Telnet/rlogin or the likes?

The ftp password could have been sniffed (man in the middle), so no matter how long the pass is, it gets stolen and ftp is clear text unless you use sftp or the likes. (dns poisoning maybe?).

What other services on that machine are in state listen? (unix/linux: netstat -patune |grep LISTEN) (dont know for windows, but you get the idea).

Maybe an exploit in one of the other services giving a shell or reverse shell access?

Are there any php files anywhere that DO NOT belong to you? (back shells?)

Also it would help to know what OS the machine in question is running, and what services (also versions).

Maybe run some sort of rootkit hunter or the likes to look for suspicious files that might have been altered or replaced.

For future reference, maybe also a host based IDS that keeps an eye on files etc...

Whatever the case, some more info would be nice to get a better picture of the possibilities.