Jeff:

When I first read your post I, too, thought of a rusty fuel tank. Sounds like that is ruled out if it was recently cleaned. Just a couple of other things to consider:

Was this car used regularly before you bought it? If not, the gas in the tank could be bad and could have fouled the plugs. Old gas turns to varnish in the tank and plugs don't like to burn it.

If the entire tank was sealed on the inside you could have a problem with the sealant plugging the pickup tube. I have heard of people sealing them shut. In your case it might be partially occluded and a small bit of debris is finishing the job.

Please post again when you find the answer.