Can you provide an option on the Add New Button page to place the newly-created visual editor button on row 2 or row 3 instead of on the first row? This could be as simple as a radio selection:
Row: o 1 o 2 o 3
Your screenshots all show a single-column new-post page. But on a multi-column new-post page, any buttons added to the default (1st) row extend beyond the mce editor window and are therefore not accessible. (Well, the 1st one might show up, but a 2nd or 3rd will disappear.)
All you would need to do is replace 'mce_buttons' with 'mce_buttons_2' or 'mce_buttons_3' for the 2nd or 3rd rows, respectively. If you used the radio selection idea, just a switch statement based on that radio choice.
For my purpose, I could edit your plugin to force the new buttons to a different row.
But for the non-coders out there, I think providing an option on the Add New Button page would be a wonderful addition to an already great plugin.