nested Shortcode doesn’t work

Shortcode:

[permalink]nested Shortcode doesn't work[/permalink]

Output:

<a href="https://wordpress.stackexchange.com/questions/18659/foobar">nested Shortcode doesn't work</a>

WordPress shortcode API sais, it’s correct:

http://codex.wordpress.org/Shortcode_API#Nested_Shortcodes

Any Ideas?

From the page you linked:

The shortcode parser correctly deals
with nested shortcode macros, provided
their handler functions support it by
recursively calling do_shortcode():

You need to recursively call do_shortcode() on any shortcode handler that could contain nested shortcodes. So for example:

function wpse18659_permalink( $atts, $content ){
    return '<a href="' . get_permalink() . '" title="Permalink to ' . get_the_title() . '" alt="">' . do_shortcode( $content ) . '</a>';
}

add_shortcode( 'permalink', 'wpse18659_permalink' );

That should handle nested shortcodes just fine.