My diagnosis above isn't right. The real problem is with the ordering of operations in pp_concat: the left and right operands are both fetched before either is copied. I have a patch that fixes it:

--- pp_hot.c.orig       2005-11-21 16:22:04.000000000 +0000
+++ pp_hot.c    2005-11-21 17:00:57.000000000 +0000
@@ -148,11 +148,14 @@
     dPOPTOPssrl;
     bool lbyte;
     STRLEN rlen;
-    const char *rpv = SvPV_const(right, rlen); /* mg_get(right) happe
+ns here */
-    const bool rbyte = !DO_UTF8(right);
+    const char *rpv;
+    bool rbyte;
     bool rcopied = FALSE;
 
     if (TARG == right && right != left) {
+       /* mg_get(right) may happen here ... */
+       rpv = SvPV_const(right, rlen);
+       rbyte = !DO_UTF8(right);
        right = sv_2mortal(newSVpvn(rpv, rlen));
        rpv = SvPV_const(right, rlen);  /* no point setting UTF-8 here
+ */
        rcopied = TRUE;
@@ -179,6 +182,11 @@
            SvUTF8_off(TARG);
     }
 
+    /* or mg_get(right) may happen here */
+    if (!rcopied) {
+       rpv = SvPV_const(right, rlen);
+       rbyte = !DO_UTF8(right);
+    }
     if (lbyte != rbyte) {
        if (lbyte)
            sv_utf8_upgrade_nomg(TARG);
--- t/op/tie.t.orig     2005-11-21 16:50:25.000000000 +0000
+++ t/op/tie.t  2005-11-21 16:52:07.000000000 +0000
@@ -578,3 +578,10 @@
 print $h,"\n";
 EXPECT
 3.3
+########
+sub TIESCALAR { bless {} }
+sub FETCH { shift()->{i} ++ }
+tie $h, "main";
+print $h.$h;
+EXPECT
+01
[download]

Just need to do some testing, then I'll send it to p5p.

Update: I've added tests and fixed a unicode bug that I accidentally reintroduced (as per the updated patch in this node), and submitted the patch.

Second update: the patch was applied (as change #26185), then Rafael noticed a subtle bug and reverted it (as change #26190), then I fixed the bug and the fixed patch was applied as change #26192. Phew!