I was under the false impression that tail numbers don't change
Tail numbers (AKA registrations) are changeable by definition since each country is allocated codes with different prefixes and formats. If an operator from country X buys an aircraft from an operator in country Y, then the tail number must will most of the time be changed to a valid tail number of country X. Depending on local laws, in some rare cases a tail number of another country will be used, for tax purposes (much more common with sea vessels). This is why some Aeroflot aircraft have VP-B* registrations that belong to Bermuda.
What does not change is the manufacturer serial number (which may be analogues to a road vehicle VIN).
I think the source of the confusion is that the Wikipedia article that you linked to uses "tail number" of civil and military aircraft interchangeably, and that is wrong. Military aircraft's tail numbers do not conform to their countries' ICAO-issued civil registration format, and they may or may not be changed whenever said air force want.
Already know that different carrier + same tail number may mean different aircraft
This assumption is wrong. Tail numbers are unique. However, they can be re-used over time.
Under what circumstances do tail numbers of commercial aircraft typically change? That is, other than arbitrary whims (which I assume are rare), when do airlines/aircraft owners go through the number changing procedure?
As mentioned above, the most likely case is when an aircraft is being bought from an operator from another country than the previous operator.
Sometimes the new operator will change the tail number even if the aircraft was bought from an operator in the same country in order to fit the registration scheme that said operator may use (for example, N737* for 737 aircraft, N747* for 747, etc).
Other than the mentioned cases above, it's impossible to answer this question in general terms. Every operator may or may not change tail numbers of aircraft it buys. An operator may even decide to change tail numbers of aircraft it already owns just because.