Hi Dave, I've cycled all around the world with my bike and it's not always easy to keep everything under 20kgs. The only time i have ever been charged was actually flying with Qantas. Yes, i did have a bike box. But I think that's another discussion.
It's a while since I travelled O/s with our tandem, but I've found with my domestic trips, VirginBlue is best for bikes. (Anecdotal evidence from other tourers within my circle indicate that they are best for o/s flights too.) They consider a boxed bike as only adding 5kgs to your luggage regardless of its weight. I load my solo bike, tent and spares into box and then tape pannier sets together (front and rear) to add to the remaining 15kg limit (20 - 5 for bike). This then means that I only wait for "two" sets of luggage at the carousel before wandering off to find my boxed bike. Haven't had a problem yet with them.