The "it works after traceroute" line was the moment I was sure it was ARP caching. Then I was just wondering if it had anything to do with AWS specifically, which could have pointed towards a serious VPC bug. That doesn't seem to be the case though. You're not weird. Just burnt by real experience.
Nice write-up. Too bad I'm not in SF. :P