Charlie and Janet, thanks for your suggestions - I have digged a bit more into the problem
The problem occurred once more, just an hour ago. Nothing peculiar going on at the server. Devices already connected to the server, wireless or by cable, continued to work, but new devices suddenly couldn't connect anymore. The dhcpd process was running, ifconfig didn't show anything special, both eth0 and eth1 were up, no errors.
I stopped the dhcpd service, started dhcpd from the command line, and all was well.
/sbin/service dhcpd stop
/usr/sbin/dhcpd -d -cf /etc/dhcpd.conf -lf /var/lib/dhcpd/dhcpd.leases eth0
Killed the dhcpd process, and started the service - no errors, but dhcpd wasn't working.
Once more, stopped the dhcpd service, started dhcpd from the command line, and everything is well again.
Strange, isn't it?