Back in 1996, Magic: The Gathering was just settling in as one of the ‘must have’ games to play on the same level of Dungeons and Dragons. While there were still some hiccups in the deck and expansion process like accidental card misprints with another game and card artwork being altered in translation, the game’s growing stature and relevance was quickly streamlining all the processes and adding on a layer of quality control that would prevent any unusual releases in the future.
So when the new Alliances expansion was due up in June of that year, no one thought there would be much of an issue coming up. But no one at Wizards of the Coast or Magic was ready for the "Marriage of Convenience" card.
The card itself had little to do with marriage. The spell was just a fun way to say that a non-white opponent's creature card could be removed with the subsequent toughness being equated into life for the player. Literally the targeted creature "got married."
Well Magic artist Phil Foglio apparently thought about it a little differently:
It was great artwork, but it didn’t quite meet the ‘dark’ and ‘foreboding’ imagery they wanted. Magic higher-ups itself deemed it "too silly" for Alliances.
Thinking quickly with a June deadline to make, artwork was traded around quickly. Foglio’s artwork was moved to the card Unlikely Alliance, which was both fitting in the tone of it all and hinting back to the the expansion.
With marriage now ruled out as an angle, the "Marriage of Convenience" card was changed to Exile. Excellent artwork by Rob Alexander was also given to the card to make it more fitting of outright removing a creature in a non-bloody way. The name itself also implied that the removed creature would be going to the artwork's fortress as a form of exile.
It actually worked almost too perfectly. The changes melded in quite well and players were none the wiser that one of the coolest cards of the expansion nearly had a hilarious marriage scene on it.
There’s a time for seriousness and a time for wackiness, and in Exile’s case, it was a trade in artwork and a name change to do the trick.
Oh, and it was also considered one of the strongest spot removal cards of its time. No biggie.