The space for MAC addreses is 281,474,976,710,656. Based on http://golubev.com/gpuest.htm, the rate for MD5 hashes is approximately 1 billion/second on a GPU.

So, in about three and a half days you could generate the whole space of MAC addresses (assuming that they only protect it with a single MD5 hash). You'd need about 1.7 petabytes to store it.

For something like this, you don't even need to generate the entire MAC address space. As of right now, there are a little more than 17000 assigned OUIs ( http://standards.ieee.org/develop/regauth/oui/oui.txt ), which means there are about 281 billion legitimately allocated MAC addresses. So, with simple filtering, you could fit that hash table into a few terabytes of storage space, and generate it in a handful of minutes.

In the ideal case, you'd only need to hash ~17000 * 2^24 MAC addresses to have a complete table, but the reality is that there are a lot of manufacturers who assign MAC addresses in products using OUIs that they haven't registered. (Registering an OUI costs US$1885, and when you're a factory working on razor thin margins, that's a lot of money.)

As an example, a $17 802.11n travel router I bought from Monoprice a few weeks ago uses 00-B0-C0 as the OUI, which has no corresponding entry in IEEE's OUI database. In the past, I've purchased cheapo no-name PCI Ethernet cards (usually with Realtek chipsets and lots of empty pads and/or through-holes on the PCBs where capacitors are supposed to go) which had similarly unregistered OUIs in their MAC addresses.

Ugh, yeah. I should have taken into consideration penny-pinching companies when doing that math. Especially when their behavior makes it hard on everyone else when the inevitable MAC conflict happens.

You could easily bring the space requirements down by storing hash chains instead of a lookup table, while still only taking minutes to reverse a given hash.

Correct. MD5 doesn't provide much security, as you can brute force the entire 48-bit space of MAC addresses rather quickly. (And as you point out, the relevant space is even less.)

They could combine the MAC with some other identifiers, like perhaps the product key from Windows or disk volume serials and hash that together.