Thanks for your post! It helped me so much!
I was experiencing the same problem as you and modifying the host file would have fixed it for me. Instead I put the proper domain name suffixes in the DNS search list for unqualified host names (My backup server and production network servers are under different domain names).
I'm taking a guess here, but it looks like Backup Exec uses Windows networking to list the servers, then turns around and does an unqualified DNS lookup to get the IP address.