I've actually been successful with bike boxes. Actually, on my present trip I flew with my bike out to Moncton (in eastern Canada). Most bike shops will let you have the box for free or for a nominal fee ($5). And you don't have to find a storage place for it and since most airports are near major cities you can find another. And it cost me to send my bike $25 (with WestJet). Keep in mind that this may very.
As for trains, I know VIA Rail will sell the box to you (they have them prefabbed). You just disassemble and pack it yourself (don't forget packing tape and electrical tape -- the eletrical tape I find it good for taping pedals together and taping smaller bits to the bike)
An alternative that I've used here in Canada is to ship it via Greyhound. Takes a bit longer but if it's not over the big Pond, works well too.