Since there was no sale, where does the money actually come from?
From the refinancing bank. It's a new loan.
How does a bank profit from this, i.e. why would they willingly help someone lower their mortgage payments?
Because they sell a new loan. Big banks usually sell the mortgage loans to the institutional investors and only service them. So by creating a new loan - they create another product they can sell. The one they previously sold already brought them profits, and they don't care about it. The investors won't get the interest they could have gotten had the loan been held the whole term, but they spread the investments so that each refi doesn't affect them significantly.
Credit unions usually don't sell their mortgages, but they actually do have the interest to help you reduce your payments - you're their shareholder. In any case, the bank that doesn't sell the mortgages can continue making profits, because with the money released (the paid-off loan) they can service another borrower.
