Browser fingerprinting is one possible way.

https://panopticlick.eff.org/

[edit: clarified that this is a solution, I have no knowledge as to whether that is what is done.]

Do you actually know that fingerprinting is used or is just an assumption?

They seem to only be collecting screen resolution, viewport size and whether ads are showing client side (tested by trying to load a file called ads.js that inserts a div into the dom). I assume server-side they combine this with user agent string and ip address.

Screen resolution & viewport size aren't being used. They were added many months ago when we first started development.

So you're just doing UA + IP? Seems like that would be plenty for your use case.