The neighbor cache in the Linux kernel isn't as simple as one would think. I'll try to explain some of the quirks with it.
There are subtle differences between an neighbor cache entry actually falling out of the cache entirely or just being marked as stale/invalid. At some point between base_reachable_time/2 and 3*base_reachable_time/2, the entry will still be in the cache, but it will be marked with a state of STALE. You should be able to view the state with "ip -s neighbor show",
pherricoxide@midigaurd:~$ ip -s neighbor list
192.168.42.1 dev eth0 lladdr 00:25:90:7d:7e:cd ref 2 used 184/184/139 probes 4 STALE
192.168.10.2 dev eth0 lladdr 00:1c:23:cf:0b:6a ref 3 used 33/28/0 probes 1 REACHABLE
192.168.10.1 dev eth0 lladdr 00:17:c5:d8:90:a4 ref 219 used 275/4/121 probes 1 REACHABLE
When in the STALE state like show above, if I ping 192.168.42.1, it will send the packet to 00:25:90:7d:7e:cd right away. A second or so later it will usually send an ARP request for who has 192.168.42.1 in order to update it's cache back to a REACHABLE state. BUT, to make matters more confusing, the kernel will sometimes change timeout values based on positive feedback from higher level protocols. What this means is that if I ping 192.168.42.1 and it replies, then the kernel might not bother sending an ARP request because it assumes that the pong meant that it's ARP cache entry is valid. If the entry is in the STALE state, it will also be updated by unsolicited ARP replies that it happens to see.
Now, for the majority of cases, the entry being in the STALE state is all you need to worry about. Why do you need the entry to be removed from the cache entirely? The kernel goes to a lot of effort to not thrash memory by just changing the state of cache entries instead of actually removing and adding them to the cache all the time.
If you really really insist that it not only will be marked as STALE, but will actually be removed from the hashmap used by the neighbor cache, you have to beware of a few things. First, if the entry hasn't been used and is stale for gc_stale_time seconds, it should be eligible to be removed. If gc_stale_time passed and marked the entry as okay to be removed, it will be removed when the garbage collector runs (usually after gc_interval seconds).
Now the problem is that the neighbor entry will not be deleted if it's being referenced. The main thing that you're going to have problems with is the reference from the ipv4 routing table. There's a lot of complicated garbage collection stuff, but the important thing to note is that the garbage collector for the route cache only expires entries every 5 minutes (/proc/sys/net/ipv4/route/gc_timeout seconds) on a lot of kernels. This means the neighbor entry will have to be marked as stale (maybe 30 seconds, depending on base_reachable_time), then 5 minutes will have to go by before the route cache stops referencing the entry (if you're lucky), followed by some combination of gc_stale_time and gc_interval passing before it actually gets cleaned up (so, overall, somewhere between 5-10 minutes will pass).
Summary: you can try decreasing /proc/sys/net/ipv4/route/gc_timeout to a shorter value, but there are a lot of variables and it's difficult to control them all. There's a lot of effort put in to making things perform well by not removing entries in the cache too early (but instead just marking them as STALE or even FAILED).
sudo ip -s -s neigh flush all) will mark entries as invalid, but not remove them from the cache. This is very counter-intuitive. IMO, there should be a flag somewhere to tell the system "really clean the cache, I am responsible for any problems that will happen from now on". – Kelby