Creating a Comment History?

You could simply modify your query to get recent posts by currently logged in user :

<?php

if( is_user_logged_in() ) :
	global $current_user;
	get_currentuserinfo();

	$querystr = "
		SELECT comment_ID, comment_post_ID, post_title, comment_content
		FROM $wpdb->comments, $wpdb->posts
		WHERE user_id = $current_user->ID
		AND comment_post_id = ID
		AND comment_approved = 1
		ORDER BY comment_ID DESC
	 ";

	$comments_array = $wpdb->get_results($querystr, OBJECT);

	if( $comments_array ): ?>
<h2>Your Recent Posts</h2>
<ul>
<?php
		foreach ( $comments_array as $comment ):
			setup_postdata( $comment );
			echo "<li><a href='". get_bloginfo( 'url' ) ."/?p=".$comment->comment_post_ID."'>Comment on ". $comment->post_title. "</a><br />". $comment->comment_content . "</li>";
		endforeach; ?>
</ul><?php
	endif;
endif;
?>

The easiest way is to have a custom page handle this.

1. Go to your theme folder
2. Create a new file, say recent_comment.php
3. Put the above code into this file, preceded by :

   <?php
   /*
   Template Name: User's Recent Comment
   */
   ?>

4. In WP’s admin panel, create a new page and select “User’s Recent Comment” when choosing a page template (should be a dropdown menu on the right
5. voila

Well, this one isn’t harder, but this one could depend on your theme, so no certain answer here.

Take a look at a link to a comment on your blog. You should see an anchor at its end, by example : #comment-672
(Same on this forum : click on the # on left side of your last post to see an anchor.)
All you have to do is modify one line of your code this way :
echo "<li><a href='". get_bloginfo( 'url' ) ."/?p=".$comment->comment_post_ID."#comment-".$comment->comment_ID."'>Comment on ". $comment->post_title. "</a><br />". $comment->comment_content . "</li>";

Of course, it won’t work if your theme doesn’t set these anchor when displaying comments on a post…

I’ve never used WP-Paginate…

Could you please show what the URL of comments page 2 looks like ?
Chances are you only need to add a parameter la &page=2 in the URL to access it, and I can help you include this in the above code…

Something like this should work :

<?php

if( is_user_logged_in() ) :
	global $current_user;
	get_currentuserinfo();

	$querystr = "
		SELECT comment_ID, comment_post_ID, post_title, comment_content
		FROM $wpdb->comments, $wpdb->posts
		WHERE user_id = $current_user->ID
		AND comment_post_id = ID
		AND comment_approved = 1
		ORDER BY comment_ID DESC
	 ";

	$comments_array = $wpdb->get_results($querystr, OBJECT);

	if( $comments_array ): ?>
<h2>Your Recent Posts</h2>
<ul>
<?php
		$count = 0;
		$page = 0;
		foreach ( $comments_array as $comment ):
			if($count++ % 0) $page++;
			setup_postdata( $comment );
			echo "<li><a href='". get_bloginfo( 'url' ) ."/?p=".$comment->comment_post_ID.($page > 1 ? '-page-'.$page : '')."#comment-".$comment->comment_ID."'>Comment on ". $comment->post_title. "</a><br />". $comment->comment_content . "</li>";
		endforeach; ?>
</ul><?php
	endif;
endif;
?>

Right, I misunderstood the whole idea. I thought your where looping (i.e. foreach, here) through all comments for a specific post, I forgot it was all comments from an author.

Anyway, after a short research, I found an easier way to do this :
get_comment_link()

<?php

if( is_user_logged_in() ) :
	global $current_user;
	get_currentuserinfo();

	$querystr = "
		SELECT comment_ID, comment_post_ID, post_title, comment_content
		FROM $wpdb->comments, $wpdb->posts
		WHERE user_id = $current_user->ID
		AND comment_post_id = ID
		AND comment_approved = 1
		ORDER BY comment_ID DESC
	 ";

	$comments_array = $wpdb->get_results($querystr, OBJECT);

	if( $comments_array ): ?>
<h2>Your Recent Posts</h2>
<ul>
<?php
		foreach ( $comments_array as $comment ):
			setup_postdata( $comment );
			echo "<li><a href='".get_comment_link($comment->comment_ID)."'>Comment on ". $comment->post_title. "</a><br />". $comment->comment_content . "</li>";
		endforeach; ?>
</ul><?php
	endif;
endif;
?>

Could be a problem caused by WP-Paginate, but since I don’t know this plugin and don’t want to test it, I can’t help you any further, sorry.

Yep, we could try this.
But to set this $per_page argument, we need to know how many comments per page you have. 😉

[edit]
Anyway :
replace : get_comment_link($comment->comment_ID)
by : get_comment_link($comment->comment_ID, array(‘per_page’ => 123))
if 123 comments per page.