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.