while it's entirely possible to design your BBEGs that way, remember that in 4e suggested advice a) how things are written for monsters is not always good for PCs, and visa versa. b) The basis for 4e monster/NPC design is about "does adding ability X serve a purpose to the story"
So with these two items in mind, you may want to double-back as to why you want to give this ability to all your BBEGs... is it really appropriate for -all- of them? I mean, do they each individually have a good reason to have the ability? Or you're giving them the ability just because they are BBEGs?
And then (because monster powers are not the same as PC powers) for those that do get it, it makes sense that it would be a recharge power because it would hinder the PC defenders if they are built around the mark ability (just like if you gave all your enemies fire resistance and immunity but you had a PC that was a pyromancer, etc - it would just lead to pointless frustration, making it more about you versus the now-frustrated players, rather than the PCs against challenging encounters)
As a PC power, no, not really overpowered because (as others mentioned above) few monsters have marks that have additional 'rider effects' like PC defenders do (where their mark ability usually carries another effect in addition to the mark).