Replace with partial match

$Version

(* "11.3.0 for Mac OS X x86 (64-bit) (March 7, 2018)" *)

expr = A^3 B^4/b + A^3 B^4 C/d;

rules = {A^3 B^4 -> Γ, A^3 B^4 C -> Δ};

expr /. rules

(* Γ/b + (C Γ)/d *)

As you point out, reversing the rules works in this simple case

expr /. Reverse@rules

(* Γ/b + Δ/d *)

More generally, put the longer rules first

rules2 = SortBy[rules, -LeafCount[#[[1]]] &];

expr /. rules2

(* Γ/b + Δ/d *)

Using Simplify with your rules as constraints works for your example inputs:

Simplify[A^3 B^4/b + A^3 B^4 C/d, {A^3B^4C == δ, A^3B^4 == γ}]

γ/b + δ/d

Simplify[A^2 B^4 C + A^2 B^4, {A^2 B^4 C == γ, A^2 B^4 == δ}]

δ + γ

There is no general solution to this problem. It is similar to what Mathematica tries when sorting the DownValues of function and like Mathematica's internal algorithm, each automatic way of sorting your rules is bound to fail for sufficiently complex or degenerated cases.

For instance, you could in more complex situations have patterns inside your rules and since they can match nested expressions, the sorting by leaf-count might fail. Consider for instance this

A^2*B^4*C + A^2*B^4 /. {A^2*B^4 -> delta, A^2*_*C -> gamma}

The first part of the second rule is similar (although it matches more than B^4) to your example, but the leaf-count is smaller. I see two solutions

(1) Like in writing a lexer with flex, you need to take care of the correct rule ordering yourself. Btw, this is done in Rubi as well. Although the goal is somewhat different there, when the Rubi package is loaded, the integration rules are being loaded in a very specific order, because otherwise, it would not work. In your case, this means you have to sort your rules so that longer matches, that contain valid matches of other rules are tested first.

(2) You can use a different way of writing rules. Instead of

{A^2*B^4 -> delta, A^2*B^4*C -> gamma}

you use

{A^2*B^4 -> delta, delta*C -> gamma}

and use ReplaceRepeated. This gives your rules a strict one-way layout. No rule is allowed to contain a portion that is a match for another rule.

A custom ordering function to sort rules:

order[a_Rule, b_Rule] := (a /. b) =!= a;

expr = A^3 B^4/b + A^3 B^4 C X/d;
rules = {A^3 B^4 -> Γ, X -> ρ, A^3 B^4 C -> Δ}

{A^3 B^4 -> Γ, X -> ρ, A^3 B^4 C -> Δ}

Sort[rules, order]

{A^3 B^4 C -> Δ, X -> ρ, A^3 B^4 -> Γ}

Using ReplaceAll with original or sorted rules does not give the desired result:

expr /. rules

Γ/b + (C X Γ)/d

expr /. Sort[rules, order]

Γ/b + (X Δ)/d

We get the desired result by Folding ReplaceAll over the sorted rules:

Fold[ReplaceAll, expr, Sort[rules, order]]

Γ/b + (Δ ρ)/d

or using ReplaceRepeated with the sorted rules:

expr //. Sort[rules, order]

Γ/b + (Δ ρ)/d

Carl's approach is the cleanest as it does not require any additional processing:

Simplify[expr, rules /. Rule -> Equal]

Γ/b + (Δ ρ)/d