DNS over SSH Tunnel

Your ipfw … line only forwards TCP traffic. Maybe add the following line?

sudo ipfw add 0011 fwd 127.0.0.1,12345 \
                   udp from me \
                   to any not dst-port 12345 \
                          not dst-port 1080 \
                          not dst-ip REMOTE_IP

It's also a good idea to add set -x (for debugging) and set -e (to fail immediately if any of the commands fail).

• One should generally use the term 'SSH tunneling' to refer to tun/tap with SSH.
• Port-forwarding is a specific form of tunneling, but it should be still only be referred to as 'port forwarding' in this context.
• Do not use SSH tunneling (as in -oTunnel and -oTunnelDevice) except for quick ad-hoc jobs.
  • TCP over TCP is a very bad idea:
    • Why TCP Over TCP Is A Bad Idea
    • Understanding TCP over TCP: Effects of TCP Tunneling on End-to-End Throughput and Latency
  • UDP over TCP inordinately adds latency to the applications that are normally making use of it. Programs that make use of UDP should have full control over their own reliability and congestion control, such as is the case for RTP.
• DNS can use TCP as a transport. It is not restricted to UDP, though that is the preferred transport.

Use sshuttle instead? sshuttle claims to handle DNS and TCP correctly, without this amount of fiddling - just the --dns option.

IME SOCKS seemed a bit old and unloved. And I don't really understand this use of ipfw and redsocks.

However I would point out that SOCKS4 doesn't support tunneling DNS, so I'm not surprised you're having problems. Subsequent versions of SOCKS do support it, so you could look at that. And apparently SSH can support SOCKS5.