Ubuntu – Proxy to restrict access to certain websites

Try the eBox Platform. It has lots of modules and functionality and can, indeed, act as a WINS server.

We do this with Barracuda Network's Web Filter, which can be integrated with Active Directory. You can also assign certain IP addresses specific permissions - it is easy enough to make sure the same computer always has the same IP address on your network via DHCP or plain old static configuration. We chose this because we liked the reporting it does, and we got a good deal.

There are plenty of competing web filter solutions, hardware, software, open source, and even cloud based Software as a Service solutions, that integrate with Active Directory - if they do that then they almost 100% do what you need.