What do you mean everything overseas is prepaid? That is rubbish. I have lived in many different countries and you can always get a phone with subscription.
We use the Mike Network - my husband has a Blackberry and I use a quite a bit older cell phone. Everything is done up through Telus and we're quite happy with them, the phones and the rate plans.