When the game notify you that 'such and such' has moved out, it is only letting you know that their former lot is now available for you to move your Sims into. Think of it as the 'Now Available' portion of a real estate system.
As for your second question. Households can separate if that is what the Sim desires. Sometimes, the Sims will stay in the game (the current town) and other times they will leave to a place where we cannot access but they are still active and can be called back from. Usually, it is un-played Sims who will leave the game 'world' but not the game. EA put measures in place a long time ago to stop 'played' Sims from having the ability to leave the game world. Also, households do not have to move as a whole. If a Sim who is a part of a household decides to leave that household leaving the others behind, they can.
SuzyCue72 is totally correct. The system which controls these actions (moving) are governed by Story Progression.
Also, a word of caution about the 'Clean Slate' reward. Using it will wipe out all information about the couple as if they never had been in a relationship. I used it with a married Sim who was wanting a divorce and the game arranged it so that they never were married or had even dated in the first place.