This might be a stupid question, but what is the range of the MAC addresses? Are these somehow leaking to the Internet with packets that a user sends (so they know where to return)?
Wikipedia is awesome: it contains a lot of useful information. In this case, the following schema:
So there are basically 46 bits for global unicast MAC addresses, for 246 possible addresses.
MAC addresses do not leak beyond your local link (machines on the same LAN as you see your MAC address, other people do not). IP addresses are used for global addressing, not MAC addresses. Exception: if you use IPv6, your machine may obtain an automatically allocated IPv6 address, and the scheme for creating such addresses uses MAC addresses, as described here. In that case, your MAC address can be inferred from the source address in the IP packets your machine emits.