I can consistently reproduce this bug with vertical or horizontal splits.

I have never worked with vte, sorry.  Is it really possible that there is no implementation to query the current physical x,y position?  _Something_ has to keep track of that information!  Only using the center x, y methodology allows that some layout patterns REQUIRE you to follow a specific path to get to a particular terminal.

Whereas, using the current physical x, y of the current terminal, I could "know" if I were on the last line of the left terminal, so that going right would take me directly to the finish terminal.  Of course, I would have to query all terminals immediately to the right whose window-based physical coordinates are within the the bounds of this one, then pay attention to ratios, etc.  Maybe.  That is just a quick brainstorm.  I'm sure you have put much more thought into it. :)

It seems possible to create a maze game out of a layout.  Here is a simple one, starting from a new window (precede all lone [ o e w ] with ctrl+shift+ and all lone [ u d l r ] with alt+):
[ (type "start" in this terminal) e o u o d o (type "finish") l ]  This gives one long left side and four rows on the right side, which doesn't seem so unreasonable.  Now, using alt-directions, navigate to the finish terminal.  The ONLY way to get there is by doing [ r d d ].  Why not [ r d d d ]?  Because the center x, y of the left terminal is lined up with the second row on the right side, rather than with the top row.  (Maybe.  Testing from further down indicates that the physical x, y may not be so reliable.)  (With my included tt.sh, you can automate this test with ./tt.sh maze1 )

Here is a layout that consistently produces a bizarre choice for alt-up:  [ o e u e e l o ]  From either bottom terminal, alt-up takes you to same destination terminal.  Seeing it happen, you will recognize that alt-up from the bottom-left terminal has zero business going to that destination.  If you split that destination terminal vertically, the behaviour seems a tiny bit more logical for this case, but still smacks of an inconsistent experience.  (With my included tt.sh, you can automate this test with ./tt.sh dirs1 )

I thought to rotate that visual shape, to make it buggy for alt-left, but instead found an even more extreme alt-up:  [ o e u e l o e ]  If you add more vertical splits at the end of those instructions, each one seems more inconsistent.  (With my included tt.sh, you can automate this test with ./tt.sh dirs2 )

[ e o l o u o e ] gives us the same visual layout, but totally different alt-up behaviour.
[[[This paragraph kept for posterity, because I didn't feel like deleting it! :)  ->  OK, I spent some time with that last pattern, then ctrl-shift-w for the last o and everything after it, then rebuilding last e's again, each time trying to find "something" to influence the final alt-up behaviour.  It still feels flaky.  (sorry)  I didn't expect to focus so much on that part, or I would have tried to automate it with xdotool. :> ]]]
I automated it with xdotool! :)

Test Machine:  AMD Athlon(tm) 64 X2 Dual Core Processor 5600+ with 4G RAM.  Ubuntu Karmic. python-vte 1:0.22.2-0ubuntu2.1. Terminator 0.95ppa2.

I will test this out in VirtualBox with Ubuntu Lucid again tomorrow.  In the meantime, tt.sh is attached.  Please let me know if it is useful at all. :)

Oh, yeah!  Bonus:  tt.sh also includes THREE automated freezes as discussed in https://bugs.launchpad.net/terminator/+bug/593290 !! :)

Code follows: