So, I'm staring the problem in the face for quite some time (though it's probably obvious to those that have encountered it before.)
Test server #1: Redhat 9
Test server #2: Redhat 7.1
Both in the same network segment.
Both using the same DNS servers.
Let the hilarity ensue!
On #1:
host ftp.lanside.net reports fine
ftp ftp.landside.net connects fine
On #2:
host ftp.lanside.net reports fine
ftp ftp.lanside.net reports Unknown Host