The problem is, that tied() doesn't work inside the FETCH method. untie() does work, but it never calls UNTIE method. (...)
Is this a bug in perl or some attempt perl is making at preventing recursion?
Presumably the latter, which makes perfect sense, IMHO. In other words, within the scope of the tied package, the scalar acts as if it was untied (as correctly reported by tied), so you can access the variable without causing infinite recursion. — You can still untie it, however.
As for the UNTIE method not being called: if you do need to execute the code of that method, you could maybe call it directly, in addition to untie, when you're doing it from within the tied package.