A 486/66 box with 16MB of RAM was more than sufficient to fill a 1.54Mb/s T1 100%! MASQ has also been known to run quite well on 386SX-16s with 8MB of RAM. Yet, it should be noted that Linux IP Masquerade starts thrashing the system with more than 500 MASQ entries.
The only application that I know which can temporarily break Linux IP Masquerade, is GameSpy. Why? When it refreshes its lists, it creates 10,000s of quick connections in a VERY short period of time. Until these sessions timeout, the MASQ tables become "FULL". See Section 7.23 of the FAQ for more details.
While we are at it:
There is a hard limit of 4096 concurrent connections each for TCP & UDP. This limit can be changed by fiddling the values in /usr/src/linux/net/ipv4/ip_masq.h - a maximum limit of 32000 should by OK. If you want to change the limit - you need to change the PORT_MASQ_BEGIN & PORT_MASQ_END values to get an appropriately sized range above 32K and below 64K.