Not only paperwork, but lots and lots of cash.
If you want to know (within reason) where an airplane started, look at the N or tail number.
If you see a US Airways 737 in Orlando that has a number that ends in AW, that airplane was a part of America West.
For the most part the legacy airlines used common sense with the tail numbers. Anything that ends in AA started with American; if it ends with TW it’s an old TWA airplane. Likewise Delta mostly uses DL and Northwest used NW as much as it could. I never could figure out Continental - they just seem to have random junk on their tails. Maybe since they are now officially United they will all get the UA tails.
The tail numbers don’t usually change unless the airline is planning on keeping the new airplane for a long time. Of course the definition of “long time” fluctuates. From what I’ve seen (strictly as a tail number observer while at work) this seems to be about 10 years or so.
Why change a tail number? No reason, other than fleet commonality and making your airline look and feel like a big player.
The piles of cash and paperwork required to do that have to please the beancounters before it will happen, of course.
My airline (FedEx) is great about this - every airplane shows up with a tail that ends in FX, FE or FD. It costs Fred Smith a ton of cash to do that, but he does.
And more to the point of the OP - no one really cares about tail numbers. But flight numbers have some special importance.
We had our first ever fatal crash over two years ago (FedEx 80 landing in Narita). We lost both pilots, and by news standards it was a minor event (only two people and some boxes? Who cares!)
But we took it seriously, and even though we don’t carry passengers the flight from Guangzhou to Narita has been renumbered. FedEx 80 will always be remembered as the flight that Kyle and Tony lost their lives, and no one wants to take that away from them.