Well I don't actually consider the options I've presented to be that far fetched.
For all the places that I've worked, the cleaners have always been part of another company, one that was contracted to provide cleaning services. There's also firms and contractors that provide bookkeeping services for small businesses. I'm sure a lot of other administrative tasks could be outsourced as well.
Having these services provided by other companies would raise the minimum salary in a company quite a lot.
The other thing companies do is set up plenty of shell/thin corporations around the world, assign the IP rights to those in minimal tax countries, and then charge massive internal fees so that all the rest of the organisation barely makes a profit. This sort of thing seems to be the same level of loop-hole as setting up multiple companies so that the CxO's can get paid more.
Of course that's forgetting that most of the CxO pay is actually in stock and options, and not so much is in cash, so I don't know how much a law capping CEO pay would do. Some notable CEO's have actually taken just $1 of actual cash for payment (because legally they have to be paid something to receive company perks).