Hardware

hardware is a 10-year-old pc: intel celeron 366/92M memory/2 100M network card
memory usage is 39% and cpu usage is barely 25%, I have only 4 pcs behind m0n0wall but every connection is extra slow(serverl seconds to establish one or just dead  dns resolution, google chrome reported ERR_NAME_NOT_RESOLVED), msn is often disconnected etc.

I've been using m0n0wall on a better pc(intel tualatin c3 1.0g /256M/2 100M network card) and worked great so maybe my current pc configuration is too low for m0n0wall to function properly?

if cpu is that low (25%) and memory (39%) is should work better.  The problems you describe could all be related to your WAN connectivity or NIC.

If you setup some local host names, I assume they resolve everytime without delay, and that the web gui works without delay or problem ?

Local host names do resolve without any delay. If m0n0wall is replaced by a router everything is fast so I guess WAN connectivity should be fine.

You might be right one of the NICs is causing the trouble, I will try to use two other NICs to see if this will help.