The actually problem was a simple router/firewall configuration from my upstream ISP that didn't pass certain traffic through one of its machines, but did through others, so depending on the path to my machine, it made it or didn't.