additional menu items not behaving

Hmm, it's working fine for me
I think I know what the issue is though: try putting the entries in in reverse order (so the largest number comes first)

I think the issue is that you're working with array keys. So when you insert something at the beginning, it has to redo all the keys for the other entries, which changes the key you have to use to add another entry. Doing it in reverse means you'll only reindex parts you won't add more things to

No, it's not really a bug per-se, but it should be better documented that order is relevant.

And I'll try to explain it a bit better.
The links look something like this:

array
(
    0 => 'Index',
    1 => 'User list',
    2 => 'Search'
)

When you add something to index 0 and index 1 (in that order), you get the following

array
(
    0 => 'thing 1',
    1 => 'Index',
    2 => 'User list',
    3 => 'Search'
)

array
(
    0 => 'thing 1',
    1 => 'thing 2',
    2 => 'Index',
    3 => 'User list',
    4 => 'Search'
)

Done in reverse order, however, it looks like this

array
(
    0 => 'Index',
    1 => 'thing 2',
    2 => 'User list',
    3 => 'Search'
)

array
(
    0 => 'thing 1',
    1 => 'Index',
    2 => 'thing 2',
    3 => 'User list',
    4 => 'Search'
)

You see how the array keys change and how that affects placement?