Daniel Lichtblau and Andrzej Koslowski posted a solution in mathgroup, which I adjusted marginally. (I like to use german identifiers, because they will never clash with Mma builtins). That's the code:
SetAttributes[termErsetzung,Listable]; termErsetzung[expr_, rep_, vars_] := Module[{num = Numerator[expr], den = Denominator[expr], hed = Head[expr], base, expon}, If[PolynomialQ[num, vars] && PolynomialQ[den, vars] && ! NumberQ[den], termErsetzung[num, rep, vars]/termErsetzung[den, rep, vars], (*else*) If[hed === Power && Length[expr] === 2, base = termErsetzung[expr[[1]], rep, vars]; expon = termErsetzung[expr[[2]], rep, vars]; PolynomialReduce[base^expon, rep, vars][[2]], (*else*) If[Head[Evaluate[hed]] === Symbol && MemberQ[Attributes[Evaluate[hed]], NumericFunction], Map[termErsetzung[#, rep, vars] &, expr], (*else*) PolynomialReduce[expr, rep, vars][[2]] ]]] ]; TermErsetzung[rep_Equal,vars_][expr_]:= termErsetzung[expr,Evaluate[Subtract@@rep],vars]//Union;
Usage is like this:
a*b/(a + a*Cos[a/b]) // TermErsetzung[k b == a, b]
a/(k (1 + Cos[k]))
The first parameter is the "replacement equation", the second the variable (or list of variables) to be eliminated:
a*b/(a + a*Cos[a/b]) // TermErsetzung[k b == a, {a, b}]
{b/(1 + Cos[k]), a/(k (1 + Cos[k]))}