Shorewall redirect rule only working for some hosts in the same network

Question

I'm trying to use Shorewall's REDIRECT action to intercept traffic destined for the firewall's port 514 (TCP and UDP) to port 5000 (also TCP and UDP), while also allowing direct traffic to the latter port as well. (The reasons aren't important, but the short version is that we're running a log aggregator as an unprivileged user, but the daemon doesn't support dropping root privileges so it therefore cannot listen on the privileged ports; at the same time we have a lot of older syslog implementations that don't allow sending to alternative ports.)

In addition to the firewall itself, there are 3 zones defined: loc (10.0.0.0/8), dmz (172.16.0.0/16), and net (everything else); the latter exists primarily to deny/drop everything from "untrusted" networks.

The relevant rules look like this:

#ACTION         SOURCE          DEST            PROTO   DEST
#                                                       PORT
SECTION NEW
REDIRECT:info   loc             5000            tcp,udp 514
REDIRECT:info   dmz             5000            tcp,udp 514
ACCEPT:info     loc             $FW             tcp,udp 5000
ACCEPT:info     dmz             $FW             tcp,udp 5000

So far so good. (There are other rules, such as allowing SSH and HTTP connections, but these are the only ones relevant to ports 514 or 5000.) Default policy is REJECT for loc and dmz, and DROP for net.

The problem is that I have many, many instances of hosts being rejected, while neighboring hosts in the same network are being redirected and accepted. For example, 172.16.0.194 is stuffing messages into our aggregator just as fast as it can, but 172.16.0.166 is having every packet rejected. Similarly, 10.140.88.150 is being accepted, while 10.192.253.4 is being rejected. Here's sample syslog messages for the latter pair:

Shorewall:loc_dnat:REDIRECT:IN=eth0 OUT= MAC=/*anon*/:08:00 SRC=10.140.88.150 DST=10.1.25.14 LEN=134 TOS=0x00 PREC=0x00 TTL=253 ID=9092 PROTO=UDP SPT=62162 DPT=514 LEN=114
Shorewall:loc2fw:REJECT:IN=eth0 OUT= MAC=/*anon*/:08:00 SRC=10.192.253.4 DST=10.1.25.14 LEN=164 TOS=0x00 PREC=0x00 TTL=254 ID=58464 PROTO=UDP SPT=514 DPT=514 LEN=144

What I find interesting is that there's very few instances of successful REDIRECTs in my log (e.g. only 1 for this host), despite the hosts that are successful sending thousands and thousands of messages, whereas there seems to be a REJECT line for every single message a rejected host is sending. It's also interesting that for many of the hosts now being rejected, they were being redirected and accepted, up until a firewall restart when we tried to add a new rule (said rule has since been removed, but we're still having the same issues). All of the current messages are coming in on UDP, but the rules need to work for both protocols.

(Also interesting is that, using tcpdump, I can see ICMP "port unreachable" responses being sent out to some rejected hosts, but not to others. I have no idea what, if anything, that means.)

My theory is that the messages from the rejected hosts are being seen for some reason as part of an ESTABLISHED or RELATED connection by iptables and therefore don't get matched to anything in SECTION NEW; however, this is the only section where REDIRECT or DNAT rules can be put, so if that's the problem I have no idea how to resolve it. (I also have no idea how to confirm or refute this theory.)

I've tried using DNAT (with $FW::5000 in the DEST column) instead of REDIRECT, however the results were identical. I also tried adding ACCEPT rules for port 514, but that had no effect on who did or did not get picked up by the REDIRECT rules.

How do I need to configure Shorewall so as to properly redirect all connections to a given port from the specified networks (zones), rather than just seemingly random hosts therein?