MySQL - selecting random row from large table

I apologise if this topic has been done to the death but I'm struggling with selecting a random row from a large MySQL table. It's a table named photos and its primary key is PhotoID. At the moment its ID's range from ~1500 (due to rows being created in testing then deleted) to ~12000, with some gaps, and I expect it will grow much larger yet.

While it's been relatively small I've been using:

 SELECT PhotoID FROM photos

...into a PHP array $All_IDs, then in PHP:

 $RandomID = $All_IDs[mt_rand(0,count($All_IDs)-1)]

then:

 SELECT /* other columns */ FROM photos WHERE PhotoID = $RandomID

This works great, I get a good range of random photos when I repeat it. However I don't think it's going to work out very efficient to load the entire PhotoID column to select one random ID, then another query to get that record, especially if I'm going to be selecting several. Likewise I'd rather not select the entire table (all columns) into an array just to pick out one. With the help of a few other StackOverflow answers I came up with the following:

SELECT MIN(PhotoID) INTO @MinID FROM photos;
SELECT MAX(PhotoID) INTO @MaxID FROM photos;
SELECT PhotoID,/* other columns */ FROM photos WHERE PhotoID >= (@MinID + RAND() * (@MaxID - @MinID)) ORDER BY PhotoID LIMIT 0,1

I thought this would work but I'm finding repeating this query several times is only giving me a short spread of ID's, in the 1500 - 1700 range, when, as above, the ID's currently go towards 12,000. I can't understand why this is?