Ok, my view on this is consistent with all of the cases presented so far...

**The symbols allowed in `Return` are those which are responsible for a transformation in the partial evaluation of the expression so far**. Of course, I'm referring only to the evaluation of the branch that includes the `Return`. There's a subtlety but I'll mention it later

Let's clarify this with your examples:

    f[x_]:=x
    f[Return[3,f]]

`f` has no attributes so, `Return` is run before any transformation is made. Doesn't work

    h[x_]:=f[x]
    h[Return[3,f]]

Again, `Return[3, f]` is executed first.

    SetAttributes[i,HoldAll];
    i[x_]:=f[x]
    i[Return[3,f]]

Here, `i` is `HoldAll` so now we start talking. 
The `i[Return[3,f]]`->`f[Return[3, f]]` is first made. `i` was the symbol responsible. Now, we run `f[Return[3, f]]`, but `f` has no attributes, so the `Return[3, f]` is run, and again, can't find `f`. Could have found `i` however.

Last one (actually second on your list, but I thought I'd leave it for last). Here comes the subtlety:
Actually, not all symbols responsible for transformations are available. When there's a transformation associated with a symbol, say, `s1`, and then there's another one AT THE SAME LEVEL, associated with the symbol `s2`, then `s1` is shadowed by `s2` and no longer available


    SetAttributes[g,HoldAll];
    g[x_]:=x
    g[Return[3,g]]

`g` is `HoldAll`, so that's a good start. First step: `g[Return[3, g]]`->`Return[3, g]` and `g` is responsible for the transformation... So, it would seem that we are succeeding.
HOWEVER, the very last transformation from `Return[3, g]` to whatever, makes the symbol `Return` shadow `g`. So, this could be fixed by just making the `Return` work at a lower level

    SetAttributes[g,HoldAll];
    g[x_]:=# &[x]
    g[Return[3,g]]

It is interesting to note that `Return[2, Return]` works, and would have worked in the previous example too.

Ok, now let's go to the cases where it actually works

    Module[{i},Return[3,Module]]

`Module` is `HoldAll`. First, there's a transformation associated to `Module`. If that transformation returned `Return[3, Module]`, then this wouldn't work. But this works. So, I choose to believe that despite what `Trace` shows, `Module` evaluated the `Return` expression internally before returning, just like our `g[x_]:=# &[x]` example.

@belisarius on the comments:

    f[x_] := g[Return[x, f]];
    f[3]

`f[3]`->`g[Return[3, f]]`. `f` was responsible. Now, `Return[3, f]` is evaluated (at a lower level in the expression tree) and success.

Bonus example:

    SetAttributes[f, HoldAll];
    g /: f[i_, g] := {i}

Now

    f[Return[2, g], g]

This actually works! Why?

`f[Return[2,g], g]` is turned into `{Return[2, g]}` BECAUSE OF `g`. Now, `Return` is evaluated (at a lower level) and that's the way the cookie crumbles

**Summary**

Imagine the expressions as trees, and the evaluation procedure as a succession of trees, and in each transformation, draw a sign pointing at the new sub-tree, with the symbol responsible written on it. If you ever have to transform that same subtree again, the previous sign is lost. When it's time for `Return` to evaluate, you go up the tree and see the signs in the path to the top. Those are the ones you can use.