> If I ping from the laptop going out to somewhere else on the network,
> -then- I can communicate properly with the laptop from the same host that the laptop pinged, for a short period of time.

and this:

> My laptop can ping anywhere out onto the network, but can't be pinged
> unless it pings first.

I see that you went to great lengths to show that it's not the network (routers, wires,configuration, etc), but for all the world, this makes me think that you've got a misbehaving or misconfigured router in front of your laptop. I say this because without ARP at all, you wouldn't be able to even have that short period of connectivity.

If I were trying to troubleshoot this I'd ping a host, `ssh` into that host in the short period of time, and then do an `arp -a` on both my laptop and that host to see what's going on. Doing a `traceroute` in both directions might also help, as might a couple of non-standard tools, [`arping`][1] and [`hping`][2].  You say that everything is on the same subnet, so `arping` working or not would convince you of your ARP-not-working theory. Since regular `ping` uses ICMP packets, `arping` checks connectivity using a different protocol. `hping` (or maybe `hping3`) lets you use UDP or TCP to do the same connectivity check. The `traceroute` (in both directions) would show if IP packets take the same route through wires and routers in both directions.

  [1]: https://github.com/ThomasHabets/arping
  [2]: http://www.hping.org/