WhatsApp showing "last online" on certain contacts, but no WhatsApp icon on Address Book app
Possible reasons:  


He might have deleted his account permanently (probably changed his number).
He might have blocked you in his account.


There is no need to remove Whatsapp to do above tasks.