So hard to narrow it down, because any of the 7 to 9 extinct genera of Hawaiian honeycreepers would do this for me; but of these, two genera in particular stand out to me: the Akialoa (Genus Akialoa, of which four species were known within historic times) and the Koa-finches (Genus Rhodacanthis, of which two were known in historic times).
Then again, it would be equally exciting to have rediscovered the Raiatea Parakeet (Cyanoramphus ulietanus) or any of the lost macaws of the Caribbean.
I suppose you can tell that I have a thing for island-endemic birds.