I've been on a similar lifestyle for about 9 years now, and I don't plan on stopping.
This may sound counter intuitive, but one thing that worked so well for me is to book a place for a shorter period (like a week), and then look for a place to stay longer. I like to feel the place for myself before making a commitment. It's also easier to negotiate a better deal when you meet the owner face to face.
Shipping travel trunks can be annoying most of the time though. Within the same country, it will be cheap and convenient. Across countries, not at all. Even within the Schengen zone, moving a large trunk can get expensive, and unless the place you stay has an elevator, it will be inconvenient as well.
Assuming you lived at your current place for a long time, you might get snail mails often. I'd arrange a way to get them scanned and emailed to me if I were you, or get one of those services and gradually change the mailing address there.