Sounds like a dodgy SRV record. Are you running integrated DNS? You could try trashing your primary DNS and then copying the secondary DNS zone file back to the server after you reinstall it. Have you checked that PTR records are being added/removed? If you perform an nslookup for the app server does your DNS reply with the correct record or does it throw up and error? Is the machine account in the AD ok? Are your DCs replicating correctly? Have you checked the GUIDs of the servers listed in the DNS, to see if dead ones are being referred to?