BIND only resolves hostname on the second attempt

[Jonathan de Boyne Pollard]

BK> My understanding is that EDNS is a Microsoft Server 2003 extension,

Your understanding is wrong.

<URL:http://homepages.tesco.net./~J.deBoynePollard/FGA/dns-edns0-and-firewalls.html>

BK> Why would a Microsoft feature break things for those of us who
BK> aren't using anything Microsoft?

Your question is a leading one based upon a false premise, and is thus 
unanswerable.