I built ypbind by hand from the nis-3.8 package with CFLAGS="-O" and the resulting binary seems to work fine. I haven't yet verified that higher optimisation is what causes the problem, but given the comments in debian/ rules about anything more than -O2 being bad news for Alpha it seems quite likely.
p.
