I don't any more efficient method. =/ I do it the same way when I do the fine work. It's quite a laod of work, but I think it pays of.
You can try to select the outer part with the magic selection (forgot the exact name...) tool and delete it once or a few times. This can boost up the process and you only need to fine-do a little bit.
@LoS: .tga has transparent background, too, I think. I'm pretty sure it does.