replacing an existing value would be simply:

$my_ordered_hash{$old_key} = $newvalue;
[download]

sub STORE
{
    my( $this, $key, $val ) = @_;
    if ( exists( $this->{hash}->{$key} ) )
    {
        $this->{hash}->{$key} = $val;
    }
    else
    {    $this->{hash}->{$key} = $val;
        push @{$this->{order}}, $key; 
    }    
}
[download]

the only really messy problem with this implementation is DELETEing - since that requires array scanning and splicing.

is there any other complications?

That's not adding a k-v pair. I'd said adding to front or back. Even adding to the FRONT is a bit edgy, since using unshift() a lot can be icky.

$_="goto+F.print+chop;\n=yhpaj";F1:eval

not like i'm trying to sound like i'm nit-picking, but how can the user 'add to the front or the back' when they are really just using a hash? the only hash operation which adds anything is the STORE, which should add to the 'end'.

just asking now because i was thinking about writing a tie for a hash as a simple kind of cache which after X additions to the (hash) cache only keeps the last-added 100 or so (since the values in this case are large and slowly-constructed objects).

d_i_r_t_y