I have had problems on my shared hosting account with Gallery 3 having the Imagemagicks convert utility processes terminated, thus not completing resize operations, and therefore leaving thumbnails and resizes at the size of the original image.

Of course you can install the Rebuild Items plugin which works. However I didn't want to rebuild my entire album of 2000+ photos, and I couldn't afford the time to open each photo, open the rebuild items page, click two check boxes to mark the resize and thumbs as dirty etc.

So a quicker a approach was required:
Firstly for this to work you need to resolve the root cause of why Gallery 3 failed to resize the resizes and thumbs correctly, which in my case was due to lack of resources available to Gallery 3. I resolved this, in my situation, by moving to a Virtual Private Server solution which would guarantee Gallery 3 what it needed to run

You need to

1. Identify the resizes and thumbs that need fixing using a MySQL query
2. Run an Update query using MySQL to set the thumbs resizes as dirty
3. Run the Gallery Maintenance "Rebuild Images" process

First gather some information:
In my Gallery the resizes should be 640 x 480. The thumbs should be 150 x 113 pixels.

Using mysql find the images that are a problem:

SELECT resize_dirty, resize_height, resize_width, thumb_dirty, thumb_height, thumb_width
FROM g3_items 
WHERE (( parent_id = '4963' ) AND 
((( resize_height > '640' ) OR ( resize_width > '640' )) OR 
(( thumb_height > '150' ) OR (thumb_width > '150' )) 
))

Then set the resize and thumb images as dirty so Gallery knows to rebuild them:
Warning: Backup your MySQL database before doing this.

UPDATE g3_items SET resize_dirty = '1', thumb_dirty = '1' WHERE
(( parent_id = '4963' ) AND 
((( resize_height > '640' ) OR ( resize_width > '640' ) ) OR
(( thumb_height > '150' ) OR(thumb_width > '150' )) ))

Note: This sets both the resize and the thumbs as dirty if either is the wrong size.

To Finish:
Finally login to the admin area of your Gallery 3 install and under the Maintenance tab find and run the "Rebuild Images" Maintenance task.

Conclusion
I ended up having 506 images that required resizing. This take about an hour for Gallery 3 to complete

Database Backup from command line

mysqldump -h mysql.yourhost.com.au --add-drop-table gallery3dbname -u g3_db_user -p > 2011-08-05-db-backup.sql