If the cup is aluminum, ammonia is a good "solvent" for the oxide and won't hurt titanium. Oven cleaner or a sodium hydroxide solution is a harsher version of the same thing. If the cup is steel, that's a different problem.

The first thing I would have tried is a good penetrating oil like Kroil and given it plenty of soak time.