This issue of getting inconvenienced because of an overbooking has only happened to me once. I’ve was platinum on Qantas for years and now relegated to lifetime gold as I haven’t flown for the longest time with them. I started flying Singapore Airlines as they had the better range of flight options for me and of course much better service. I’m now in their top 1% of frequent flyers. At the time this happened though (from memory in 2006) I didn’t have much status with them. I was in Singapore and was travelling to Melbourne with a colleague. We were not late checking in but obviously amongst the last. The airline staff approached us before we even reached the counter and queried were we flying to Melbourne. Once we acknowledged that we were, they told us a rare case of being overbooked with no no-shows. They offered us a hotel and same flight next day, a much later flight same day, or a flight via Sydney with domestic connection which would get us to Melbourne only about 3 hours late. All offers came with upgrades to first class, US$400 cash, US$200 in onboard purchase vouchers, and a little pack of SQ goodies like pens, etc.
We felt very looked after and really enjoyed the first class flight via Sydney.
Its not that hard to delight and surprise your customers when you have bad news for them.