In my experience, any strongly alkaline cleaning agent will dissolve coffee gunk nicely.
You can buy fancy cleaning products specifically made and marketed for that purpose, like your "coffee pot cleaner powder", but just plain old sodium hydroxide (soda lye, caustic soda, NaOH) or sodium carbonate (washing soda, Na2CO3) solution with a bit of dishwashing detergent mixed in will do the job just as well. Or you can just use dishwasher detergent, most of which are highly alkaline.
Safety warning: It should go without saying, but strong alkaline solutions are caustic. They won't kill you if you touch them, but they can cause irritation and nasty chemical burns if you get them on your skin and don't wash them off ASAP. If you get some in your eyes, despite the goggles you really should have been wearing, also wash it off with lots of water and go see a doctor.
Also, don't use alkaline substances on aluminum, or on anything else that's not dishwasher safe. Steel and glass and most plastics should be fine, though.
After dissolving the coffee stains with the alkaline cleaning solution and draining it, you'll want to rinse your pot with a mildly acidic solution to neutralize any alkaline residues. This will get rid of the soapy taste you complained about.
Dilute citric acid or acetic acid (clear vinegar) should work fine, as will any descaling agent suitable for use with cooking utensils. Just rinse the pot thoroughly with the acidic solution, and then once more with water only, and let it dry.
The acidic rinse will also help dissolve any limescale that might have accumulated in your pot alongside the coffee residue. In fact, if you live in an area with hard water, you might even want to consider a three-step wash: first acid to remove limescale, then alkaline to wash off the coffee residue, and finally mild acid again to neutralize any leftover alkaline cleaning solution. I haven't tested that myself, since the water around here is pretty soft, and so limescale is rarely an issue. But I suspect it might be worth trying.
Also, where possible, simple mechanical scrubbing with a sponge, with or without any chemical cleaning agents, will help a lot in removing persistent coffee stains. (Do make sure to put on rubber gloves before sticking your hands in the caustic soda solution, though!) In fact, for things like coffee cups and spoons, I've found that a good scrubbing with a rough sponge and some dishwashing soap does the job quite nicely. The chemical methods are really only needed in extreme cases, or for hard-to-reach spots e.g. in thermoses where mechanical cleaning would be difficult.