This sense of the word mistress has its origins in the conventions of medieval courtly love. The lover knelt (literally or figuratively) before his beloved and swore to serve her as a vassal; she was his mistress in the sense that he was her servant. The three earliest citations the OED offers for this sense all convey this aspect of the relationship:
c1425 in R. H. Robbins Secular Lyrics 14th & 15th Cent. (1952) 152 Now good swet hart & myn ane good mestrys I dew recumend me to yower pety.
c1450 (1375) Chaucer Anelida & Arcite 251 Me, that ye calden your maistresse, Your sovereyne lady in this world here.
1509 S. Hawes Pastime of Pleasure (1845) xviii. 83 You are my lady, you are my masteres, Whome I shall serve with all my gentylnes.
Within the courtly love convention it was the lady, not the man, who was always married; a properly-conducted courtly love affair was unthinkable without a jealous husband to be circumvented, of any rank from King Arthur downwards. It was her unavailability that made the relationship qualify as romantic; the lover could be married or not - it made no odds. It was also established wisdom that, even should it subsequently become possible to marry the lady (i.e. if she were widowed), no sensible man would do such a thing - because in the Middle Ages a husband was the master of his wife, not her servant. For courtly lovers to marry would involve either a brutal reversal of roles or an utterly unseemly continuation of romantic roles into married life.
I don’t think there has ever, at any time, been any implication that a man who had a mistress was necessarily married to someone else.