Difference between ping timed out and destination host unreachable

First we need to understand how packets are sent.

When a host or router tries to send an IPv4 packet* it first looks up the destination in it's routing table. Based on the routing table it determines the "next hop IP address" and interface. For a machine on a local subnet the "next hop IP address" will be the IP address of the destination, otherwise it will be the IP of a gateway.

What happens next depends on the interface type. Assuming it's an Ethernet or similar interface the network stack needs to determine what MAC address to send the packet to. To do that it looks up the "next hop IP address" in the ARP table for the interface. If it finds a valid entry then it fills in the MAC address and sends the packet out over the Ethernet interface.

If it doesn't find a valid ARP table entry then it will begin the ARP process to try and create one. In the meantime packets destined for that next-hop IP address will be queued up until the system knows what MAC address to send them too.

If the ARP process times out then on many platforms, any queued up packets will be rejected with a "destination host unreachable" ICMP message (some platforms just silently drop the packets).

Eventually entries in the ARP table time out and need to be refreshed.

On hosts/routers without a default gateway you can also get a "destination host unreachable" reply generated if there is no routing table entry, so the system doesn't even know what interface to ARP on.

---

So what happens when you power cycle a machine and ping it?

At first you likely already have a valid ARP table entry. Your machine puts the packets on the wire but they never get delivered because the network stack on the destination is down. You get "Request timed out" (with microsoft ping, linux ping doesn't display the lack of response at all).

Later the ARP cache entry times out. The hop before the box you power cycled (may be your client box or a router) tries to do a new ARP lookup but fails, so it bounces the packets with ICMP errors. Often you see multiple packets get queued up and bounced at the same time.

Finally the network stack on the target box comes back up. ARP succeeds and the packets are sent to the target which replies to them.

* With IPv6 the principles are similar but the details are different.