The original problem description sounds awfully like ARP table exhaustion.
We ran into this at my previous job where we used a load of consumer-grade access points for temporary field use. We could get about 26 devices running before this sort of oddness crept in. Eventually we got a D-Link engineer to confirm the ARP limitation.
There was nothing in the router's settings or status pages to suggest a limitation - for example, DHCP would happily offer a full /24's range of addresses no problem. It'd just freak out when >26 were in use at once. This sorta makes sense -- there's nothing intrinsic to the WiFi, Ethernet or DHCP implementation that has a limit -- the device simply can't keep more than a few dozen IP-to-MAC entries in RAM at once in order to route between them.
This is one of the many reasons I chose to keep my modem, router, switch and AP duties in separate lumps of hardware.
[edit: I just did a cursory search for VMG8324 and ARP. Looks like the ARP table can at least be viewed via the web interface. Might be worth counting the entries and seeing if you get an 'interesting' number - a power-of-two, or power-of-two-1, or a round decimal number. Also see if the table's missing a device that you're struggling to reach after it's randomly lost connectivity]
[edit2: I see ARP's already been discussed and discounted(?) - never mind me!]