Windows Server 2012 DHCP not working sometimes

Are you sure those 169.254 address are being assigned via DHCP by the modem? Those aren't private subnet addresses, they're link local autoconfig addresses. They're supposed to be used by hosts that don't have a static IP and can't reach a DHCP server to get an authoritative address.

I would guess that your DHCP service isn't working and that the hosts are configuring themselves with that address range.

If those are Windows hosts, does ipconfig /renew return immediately with success or does it time out?

I'm assuming that you are only using IPv4--if not, you need to check things in both IPv4 and IPv6.

I'd start by checking these in the DHCP server:

1. Make sure that you don't have any policy settings that would prevent such devices from being assigned an IP address.
2. Make sure that you have DHCP options set.
3. Make sure you can ping to the server from the OS X devices (and visa-versa).

Follow up questions:

1. Are OS X clients using wireless or are they hardwired in? If wireless, have you tried hardwired?
2. What functions were served by the gateway/router provided by your ISP? Was it also your wireless access point? If so, it might not know to forward DHCP requests on to the new DHCP server. Do you have multiple devices plugged in directly to the gateway? If so, the ISP equipment might be interfering with a wireless access point that is passing through it.
3. What does your network topology look like? Do you have everything plugged in to a switch?