The actual output is Function[0, 999][0]. I have guessed (I hope correctly) that the expected value was 999 as from Function[a, 999][0].

In Trace[f[999], TraceOff -> Message], the essential part that is responsible for h[0] is just

h$94073[a$_]:=Function[a$,999][a$]

which can be rewritten more friendly and equivalently as

h[a_] := Function[a, 999][a]

and the problem is still what should be h[0].

Actually Module and g are irrelevant. What I am doing is building a minimal example.

The example can be further minimized. h[0] actually calls

h[0] /. h[a_] :> Function[a, 999][a]

but h is irrelevant as well, so the example further simplifies to

0 /. a_ :> Function[a, 999][a]

(At each step, the value is still Function[0, 999][0].)

By definition of RuleDelayed, what actually occurs is:

Unevaluated[Function[a, 999][a]] /. a -> 0

that is, the replacement occurs before Function can do anything, hence the annoying but very legitimate output.

Had the original programmer been more simple minded, he would have written:

In[1362]:= h = Function[a, 999]

or even

h=Function[999]

so that

In[1363]:= h[0]
Out[1363]= 999

In conclusion, I think that in this case the Wolfram language is perfectly consistent but I am eager to learn my mistake.

The actual output is Function[0, 999][0]. I have guessed (I hope correctly) that the expected value was 999 as from Function[a, 999][0].

In Trace[f[999], TraceOff -> Message], the essential part that is responsible for h[0] is just

h$94073[a$_]:=Function[a$,999][a$]

which can be rewritten more friendly and equivalently as

h[a_] := Function[a, 999][a]

and the problem is still what should be h[0].

Actually Module and g are irrelevant. What I am doing is building a minimal example.

The example can be further minimized. h[0] actually calls

h[0] /. h[a_] :> Function[a, 999][a]

but h is irrelevant as well, so the example further simplifies to

0 /. a_ :> Function[a, 999][a]

(At each step, the value is still Function[0, 999][0].)

By definition of RuleDelayed, what actually occurs is:

Unevaluated[Function[a, 999][a]] /. a -> 0

that is, the replacement occurs before Function can do anything, hence the annoying but very legitimate output.

Had the original programmer been more simple minded, he would have written:

In[1362]:= h = Function[a, 999]

or even

h=Function[999]

so that

In[1363]:= h[0]
Out[1363]= 999

In conclusion, I think that in this case the Wolfram language is perfectly consistent.

In general the rule replace system gives a lot of freedom and if misused in intricate situations it can give surprising results.