Recent Posts titles not working with Qtranslate

Qtranslate works probably with a filter on the_title. So you have to use functions that make use of that filter, not the raw post title.

Example, not tested:

foreach( $recent_posts as $recent ) {
    printf(
        '<li class="lastposts"><a href="https://wordpress.stackexchange.com/questions/129891/%1$s" title="%2$s" >%3$s</a></li>',
        get_permalink( $recent["ID"] ),
        the_title_attribute(
            array (
                'post' => $recent["ID"],
                'echo' => FALSE
            )
        ),
        get_the_title( $recent["ID"] )
    );
}