Suppose that you have an ISP that only allows you to connect one device to their modem. (This used to be very common.) Suppose that you want to connect a different device. (Again a common desire.) Suppose that you spoof the MAC address of the original device so that you can connect. (This use case is a big part of why consumer electronics added the ability to spoof MAC addresses.)
Under federal law, you've now committed a felony for which you can serve jail time. Your access to your ISP's network is unauthorized.
Let me make this personal. This is not a random use case. I have done this. If anyone had cared, I could be charged with a felony. I could serve jail time, for accessing a network that I paid for in a way that I thought was pretty fair. (My "crime" being that I wanted to attach a wireless modem to the network so that I didn't have to have a wire connecting my laptop while I was using it. OK, I was bad, my wife and I could both use computers at the same time.) I didn't think I was doing anything wrong. It was a pretty common act. It was still a felony.
So no, randomizing your MAC address is not illegal. But the line between legal and a felony here is awfully easy to cross.