How to delete cached transients from a widget instance properly?

Use a widget cache and forget the actual number of active widgets.

In your widget add this to your method widget():

public function widget( $args, $instance ) 
{
    // get the cache
    $cache = wp_cache_get( 'UNIQUE_WIDGET_IDENTIFIER', 'widget' );

    if ( !is_array( $cache ) )
        $cache = array();

    if ( ! isset ( $args['widget_id'] ) )
        $args['widget_id'] = $this->id;

    if ( isset ( $cache[ $args['widget_id'] ] ) )
        return print $cache[ $args['widget_id'] ];

    // go on with your widget logic, put everything into a string and …

    $cache[ $args['widget_id'] ] = $widget_string;

    wp_cache_set( 'UNIQUE_WIDGET_IDENTIFIER', $cache, 'widget' );

    print $widget_string;
}

And in your widget’s __construct() register the flush actions:

add_action( 'save_post',    array( $this, 'flush_widget_cache' ) );
add_action( 'deleted_post', array( $this, 'flush_widget_cache' ) );
add_action( 'switch_theme', array( $this, 'flush_widget_cache' ) );

The callback in your widget class is just a simple …

public function flush_widget_cache() 
{
    wp_cache_delete( 'UNIQUE_WIDGET_IDENTIFIER', 'widget' );
}

Transients time out even if nothing has changed. That’s not what you need here.
Don’t forget to replace UNIQUE_WIDGET_IDENTIFIER with your own value. 🙂