Always...two deployed fine, one failed. Strangely, the failed server wasn't always the same. At times, it even exhibited a sort of round-robin behavior. First 4, next attempt 5, next attempt 3, then back to 4.
I was not able to replicate this in my dev environment until, instead of deploying the solution via the Central Admin Application, I deployed it using the stsadm -o deploysolution command.
The stsadm command clearly states "Timer job successfully created," but upon checking the Central Admin Application for status I found "Error". This pushed me to investigate the Windows SharePoint Services Timer service and led me to believe it was incorrectly caching something.
I followed the steps highlighted in the resource articles and magic, it's fixed.
For the record, I did delete the cache.ini file without problems. Also, depending on if you're using Server 2003 or 2008, the cache files are in different places. Just use the %ALLUSERSPROFILE% token in the address bar of Windows Explorer and you should be good to go after that (e.g. %ALLUSERSPROFILE%\Microsoft\SharePoint\Config).
References:
Clearing the Sharepoint configuration cache (Joris Poelmans)
Clearing the SharePoint Configuration Cache (Joe Rodgers)
