Quoting upstream commit:
http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=d0ebf133590abdc035af6e19a6568667af0ab3b0

  If a rule using ipt_recent is created with a hit count greater than
  ip_pkt_list_tot, the rule will never match as it cannot keep track
  of enough timestamps. This patch makes ipt_recent refuse to create such
  rules.

Version-Release number of selected component (if applicable):
kernel-2.6.18-164.el5

Steps to Reproduce:
Outline in the upstream commit, this variant using TCP connections instead of
UDP connections worked little better for me:

iptables rules:

iptables -F
iptables -A INPUT -p tcp --dport 1235 -m recent --remove --name test
iptables -A INPUT -p tcp --syn --dport 1234 -m recent --set --name test
iptables -A INPUT -p tcp --syn --dport 1234 -m recent --update --seconds 60
--hitcount 20 --name test -j REJECT

run testing server as:

while : ; do nc -l 0.0.0.0 1234 ; done

client side:

# remove previous recent entries to get a clean state
echo 2> /dev/null | nc 127.0.0.1 1235
cat /proc/net/ipt_recent/test

for i in `seq 1 30`; do
  echo $i | nc 127.0.0.1 1234; sleep 0.2
done

When hitcount 20 is used, you can see only 19 connections to the server are
allowed.  Raising hitcount to 21 (assuming default ip_pkt_list_tot), unlimited
number of connections are allowed.

After the fix, an attempt to create rule with hitcount higher than
ip_pkt_list_tot should result in error:

  iptables: Invalid argument