A little hunting around showed that some of the common included php files on the website had been modified, such that when the page was accessed using google-bot's user-agent values, the page added the extra spam content. This made Google index the website with the spam title instead of the real one. Here is a great detailed post on this hack on Google's Webmaster Central website.
The hack had modified the PHP files by adding a single line which looks like this:
error_reporting(0);eval(base64_decode('JGxMOXdG..long long string..'));
When the string is decoded, it shows HTML content with all the spam links.
The modified time of the file was the same as other files, so who ever did this made sure the modified time was set to the original one. I removed the extra content and placed a request to delete the page from Google's cache (For details on removal, look at http://www.google.com/support/webmasters/bin/answer.py?hl=en&answer=164734&rd=1 under "The page has changed and I want the outdated information removed")
Everything worked fine. Till a few days ...
Google results again started showing weird results, and another hunt showed similar strings added. Removed the content, was fine for a few days and again ... This was becoming painful and stressful. I had now got into this habit of logging into the shell and running
grep -RI base64_decode . | more
to see if there were any long entries, and then replacing that file with the untainted one from my backup. But the root cause of the problem was still unknown.
And then there was one particular file which on my machine was called groups.php
This had another eval(gzinflate(base64_decode('...'))) and when run, it showed a page called "r57shell 1.40". This page gave full access to whatever PHP exposed under the web users permissions, which meant one could access the filesystem, database, mail, ftp and what not. This was brilliant and I would have admired it more had it not been so harmful to me. I guess this was used to periodically modify various php files on my website to inject spam content. This may have been added during the brief period I was using ftp instead of sftp. I am not sure yet though. A couple of other similar harmful files also surfaced, (called white.php and added to punBB's lang/eng/ directory) which had some other back doors opened.
Removed these files and started searching for a solution which would track such problems and alert me, when I came across an "Anti Virus" link on a2hosting's CPanel. Added back the problem files, ran the AV (powered by ClamAV) and sure enough, those files were detected as Trojans. I wish I had known about this a couple of months back.
To prevent further such attacks,
all file permissions were changed to 644 and directory permissions to 755
all ftp users were removed and only sftp will be used henceforth
Also created a small php file which would show files with base64_decode in it
$output = shell_exec('grep -RI base64_decode /my/homedir/www');
I hope this post helps others who face similar problems.