Several old hostnames were deleted from the console, but re-appears after a few days. Is it possible? And how can these deletion be made permanent. 

It's probably discovery by one of the configured discoveries. To see which one discovered it look in the properties of the device and look at the Agent Name property to see which discovery s finding the device again.

The will re-appear if the client is still active and can reach the MP (heartbeat discovery).