Does the description of time or location "W maju..." always come first in the sentence, or is that just the dominant scheme in a flexible phrase order?
This is not typical word order, imho – I would normally write "One kupują ubrania w maju" and as it is, the sentence puts emphasis on clothes, so it would best work as, for example, "W maju one kupują ubrania a w czerwcu meble"(They buy clothes in May and/but furniture in June).
I think this sentence in both orders is equally likely to happen (it might be a personal preference, or a regional thing).
One kupują ubrania w maju answers a question when do they buy clothes? W maju one kupują ubrania answers a question what do they buy/do in may?
Also I think it is worth noting, that if it were a sentence with omitted subject: "W maju kupują ubrania" is more likely, because we prefer to keep verb in the middle of setence, and to keep object behind verb.
Well, given right kind of context, virtually all word order in Polish can be made to "fit". ;-) I just meant that, if I ware to came up with a single, bereft of any context sentence for a language teaching course, "One kupują ubrania w maju" would be my choice some 99% of times, compared to "W maju one kupują ubrania" – that is not to say that this word order is in any way wrong or anything, as you already pointed.
But in the end, maybe that is indeed just my personal preference, I don't know. ;-) Important part is, that this exchange answered JackyDW's question: There is no requirement to put "W maju" at the beginning. :-)