For anyone looking into the same problem, I've just discovered that I don't have to remove the permalink structure, I can just append the &p=[post_id] directly to the preview link provided for success. Works for my permalink structure anyhow which is fairly simple /%postname%/.
Dominik: one way that you may be able to help fix this in future releases is by adding the preview_post_link and/or preview_page_link filters to your get_preview_link method.
An example from /wp-includes/meta-boxes.php : post_submit_meta_box() is as follows...
$preview_link = get_permalink( $post->ID );
if ( is_ssl() )
$preview_link = str_replace( 'http://', 'https://', $preview_link );
$preview_link = esc_url( apply_filters( 'preview_post_link', add_query_arg( 'preview', 'true', $preview_link ) ) );
That is the code used for the preview button in the submit/publish metabox on the edit post page. With that filter in place in your plugin, those of us affected could hook into it and add the required p var.
Hope that's a helpful start.