Tricky question! It will be hard for us to give certain answers, we may only guess that they might employ fingerprinting techniques that match in both VMs. For example, the VMs might both have have the same operating system, user agent string, set of fonts, give the same canvas fingerprint, have similar CPU performance, etc. It might also be that they found the local IP address to be in the same range, if that was obtainable via WebRTC.
If you did the IP routing correctly (such that the IPs that you used are not the same), and the VMs are indeed clean (so there are no cookies or localStorage), and it's not a very esoteric setup (so your user agent by itself is already unique), then as far as I know, they can only rely on fingerprinting techniques.
You say you 'registered': maybe the email address domain matched as well? When all these factors are combined, it may give a pretty accurate result.
Note that the VMs can very easily become unclean. If you checked that the IP addresses differ by going to tell_me_my_ip_please.com
, that website might have tracking scripts. A Like button from Facebook, Google Analytics, an embedded YouTube video, advertisements, etc. are very widely used and can all track you. If you did this to check that it works and then clone the VM, you now have two linked VMs. If you did not, then they'll not be able to link the VMs directly, but they may also do the fingerprinting and combine the information of "no cookies, using this operating system and browser, from this country, etc." into a profile like "probably a white male from Belgium". This information is often reported to website owners, and could also loosely link your visits. It's a little more far fetched, but could be an additional datapoint on which they based their decision.
You might get a better answer if you are able to share the software/website you were trying to use, but from your question it sounds like it's a small, commercial party that might see this post and identify you, so I assume you can't share that.