This is very late, and a non-answer, but I wanted to follow up with exactly what I did in case anyone else is interested.
I was working with some very weird embedded hardware that doesn’t have a MAC address assigned at manufacture. That means we needed to assign one in software.
The obvious solution is to have the user pick a MAC address that they know is available on their network, preferably from the locally-administered range, and that’s what I did. However, I wanted to pick a reasonably safe default, and also attempt to warn the user if a conflict occurred.
In the end I resorted to picking a random-ish default in the locally-administered range, chosen by making some hardware readings that have moderate entropy. I deliberately excluded the beginning and end of the range on the assumption that those are moderately more likely to be chosen manually. The chances are that there will only be one of these devices on any given network, and certainly less than 20, so the chances of a conflict are very low, albeit not as low as they could be due to the somewhat predictable random numbers.
Given the low chances of there being a problem, and despite the excellent answers above, I decided to dispense with the conflict detection and make do with a warning to the user to look out for MAC conflict problems.
If I did decide to implement conflict detection, then given that I control the whole network stack, I would probably look out for excessive unknown or missing packets, and then trigger a change of MAC address or warn the user when that happens.
Hopefully that will help someone else somewhere – but probably not!