use strict;
use Tk;

use Data::Dumper;

my @data = (qw( ccc eee ddd aaa aaa ccc ddd ddd bbb ddd eee ggg fff));
my %seen;

# Create & configure text widget...
my $top = MainWindow->new;
my $list = $top->Scrolled('Listbox')->
    pack(-side=>'right', -fill=>'both', -expand =>1);

my $ref;
$ref = $top->repeat(700, \&addItem);

sub addItem
{
    my $item = shift(@data);
    if(!$item) { $ref->cancel; return };
    print STDERR "$item\n";
        # Selected items (by name)
        my @selected_items = map {$list->get($_)} $list->curselection;
        print "Selected items: @selected_items\n";
    if(! $seen{$item}) {
        my @new_selection_order = sort keys %seen;
        # Map names to list position
        my %new_selection = map {($new_selection_order[$_] => $_)} 0..
+$#new_selection_order;
       $list->delete(0, 'end');
       $list->insert('end', @new_selection_order);
           # Set selection(s)
           print "New indexes should be @new_selection{@selected_items
+}\n";
           $list->selectionSet($_) for @new_selection{@selected_items}
+;
    }
    $seen{$item}++;
}

MainLoop();
[download]

I'm thinking that I'll have to do a binary-search-and-insert

I think you don't need to get too fancy with the inserting algorithm. I simple linear search should scale well up to at least several thousand items in the listbox — and more items isn't particularly good GUI design anyway...  (also, my guess would be that reconstructing the listbox content from scratch for every insert operation isn't necessarily faster (I haven't benchmarked it, though)).

So, for all practical purposes, something like this might do (but you could of course implement a binary search, too, if you like):

...
sub addItem
{
    my $item = shift(@data);
    if(!$item) { $ref->cancel; return };
    if(! $seen{$item}) {
        INSERT: {
            for my $idx (0 .. $list->size()-1) {
                if ($list->get($idx) ge $item) {
                    $list->insert($idx, $item);
                    last INSERT;
                }
            }
            $list->insert('end', $item);
        }
    }
    $seen{$item}++;
}
[download]

Moreover, not erasing the listbox content every time would also save you from having to readjust the current scroll position.

#!/usr/bin/perl -w
use strict;
use Tk;

my $mw = Tk::MainWindow->new( -title => 'Listbox' );

my @array = ('A'..'Z');

my $lb = $mw->Scrolled('Listbox',
             -listvariable => \@array,
             )->pack();


my $b  = $mw->Button(
    -text    => 'Delete B',
    -command => sub{ del_it('B') },
)->pack();

MainLoop;

sub del_it {
    my $remove = shift;
    @array = grep { $_ ne 'B' } @array;
}
[download]