Why index is not used with order by?
David Spillett's answer is correct in all points, except for the "encouraging" suggestion.

Here's a way to not only encourage but (in almost all versions) force the optimizer to choose a plan that uses the wanted index to find the 50 rows - and only after that perform the join. It can't always be used but the FOREIGN KEY constraint assures that in this case the two queries will produce identical results.
I call this technique "first LIMIT, then JOIN":

SELECT     p.*, ps.*           
FROM       ( SELECT     *
             FROM       productStore 
             ORDER BY   storeTitle 
             LIMIT 50 
           ) ps 
    INNER JOIN product p 
        ON p.productUUID = ps.productUUID       
ORDER BY   ps.storeTitle ;