Non conosco C quindi a livello di codice non ti posso dare una mano pero posso suggerirti alcuni spunti:
La risoluzione dei nomi la attui per mezzo una query DNS (ipotizzo per mezzo di gethostbyaddr()), esatto?
Invece di mandare subito la query perchè non pinghi dapprima tutti e 255 gli host? Successivamente effettui la query DNS ai soli host che risultano essere up.
Per effettuare più operazioni in contemporanea esiste il multi threading, sicuramente implementabile in C, componente onnipresente in qualunque scanner analogo, ma per soli 255 host interni alla tua LAN non credo che tu ne abbia veramente bisogno.