Well, interestingly enough, this issue went away with as pfSense reboot. I was having these problems about 1 time per hour before, now it's been 24hrs since the reboot and it hasn't happened a single time.
Not sure what was messed up, guessing it was some routing or state table issue, but oh well it seems OK now.