polo1, that bill sounds huge. Are you not on a bundled package? If you are that heavy a user of the phone I'd look into an unlimited pack with whatever provider you choose.
As some of the others said you have to have an eircom line to switch to some of the other providers as they piggybank on eircom's network.
Vodafone and UPC are eircom's two main rivals.
If you can get UPC tv in your area they may be able to provide phone and broadband too. They may be the only one's that can provide the service without active an eircom line other than mobile broadband.
If you do have to go back to them make sure you bundle your pack and have the last laugh. Their ultimate pack (24mb broadband, line rental and unlimited local & national calls with 30 mins free mobile calls) is €60 a month, €55 for the first 6 months according to the website so you could easily bring your bill down. Use someone like 13434.ie for international calls and either add a mobile bolt on from eircom or use your mobile for mobile calls.
Their €20 demand for reconnection will be wiped out in the first bill.
Then switch if you like. Once you have the line reinstated you can pick and choose.