You should not have any issues with this. Sounds like you need to check your document DPI and adjust it accordingly to fit with the one used in the images. otehrwise you'll always end up with antialaising and resampling artifacts even with automated placement due to how AI works on inches, not actual absolute pixels.
Assuming the "images" are already arranged in rows and columns, and the spacing is the only remaing issue, I'd use the Distribute Spacing tools at the bottom of the Align panel (panel menu > Show Options). Obviously, with "~5,000" objects, this method is no one-step easy button, but some endeavors inescapably take time.
Also assuming the top-left is a logical stationary target point:
Zoom out and marquee-select across the entire top row.
With all the top-row items selected, click the left-most one to set it as the key object.
With the default spacing value of 0 already set, click Horizontal Distribute Space button.
With all the top-row items still selected, choose Object > Group.
Repeat steps 1 through 4 on each row.
Click the top row-group to set it as the key object.
With the default spacing value of 0 already set, click Vertical Distribute Space button.
Note: If the overall grid is taller than it is wide, it would take less time if you swap the orientation and do steps 1 through 4 column-by-column (using Vertical Distrbute) rather than row-by-row. Basically, just work in the shorter direction. If the grid is square, it won't matter.