This probably isn't all that much help to you, but when I run your first sample code I get the expected output:

a/a/b
a/a/b

a/a/b
a/a/b

a/a/b/a
a/a/b/a

a/a/b
a/a/b

a/a
a/a

a/b
a/b

a
a
[download]

Perl 5.8.0 on HP-UX; XML::Twig v3.15.