How can I use a custom prefix for international calls? In my country, we have to use a prefix before dialing an international number, depending on which provider we use. For example, I use an international calling company for which I have to dial 019 before dialing the international number.

Now, having to edit each and every international phone number in my address book to add a 109 would be annoying. And when I move providers, having to do the whole process again would be very annoying.

Is there a way to tell Android, "every time you see a +, just dial 019 instead"? Or any other solution?

(I use Cyanogenmod.)
The only apps I have found to be able to do this kind of editing are SIP dialers like CSipSimple and SipDroid. They integrate into the regular call setup and can run a set of rewrite rules and filters to decide where and how to place the call.

I believe both can do this even for regular (cell) calls, and even when no SIP provider has been configured.