painting an aluminum/carbon frame
Your assumptions are right on, the carbon fiber stays are definitely our biggest obstacle. They prevent you from being able to powder coat the aluminum, the risk of damaging the carbon fiber from heat in the process is too great.

A professional in town should be able to properly mask the carbon fiber and sandblast or glass bead blast the aluminum. I believe glass bead blasting is the preferred option and is supposed to be gentler. Then comes the new paint job.

As usual, Sheldon has quite a bit of information on the subject: http://sheldonbrown.com/paint-prep.html