I asked about this at the blood clinic once. The answer I got was that the questionnaires are really secondary to blood testing, which is done on every donation.

The questionnaires simply

(a) weed out the people who are ineligible and honest about it (and there's no salient incentive here for people to lie*);

(b) provide extra "risk factor" information on top of the tests.

Note that being gay, or having lived in Africa, are risk factors, but are not considered dealbreakers. Probably both in combination would be a dealbreaker though.

(*The only real incentive to lie here is social pressure, e.g., your whole office is donating and you don't want your AIDS to be known about, which is controlled by allowing the donor to privately put a "No" barcode sticker on their sign-in form, which blindly disqualifies their blood without identifying them by name to any staff or patients present.)