I hate saying this... but it seems that the Windows Scandisk tool is better than any of Mac's disk tools (Disk Utility, fsck) at fixing disk problems.
I finally connected my external hard drive to a Windows system and ran Scandisk. That fixed all the problems with my hard drive. And now the hard drive mounts fine on a Mac too.
Sorry Apple!!! But this one goes to Microsoft :-(