Hmm I must say I was surprised at the results! Unfortunately, this is beyond my working knowledge of SQL, so I can only speculate (and suggest a PHP workaround).
I don't know why this happens, and you might have found a bug. It could also be that this does not follow the SQL spec for joins, even though MySQL lets it pass with undefined results. Compare your query to something seemingly similar,
SELECT ...
FROM ...
LEFT JOIN (SELECT value FROM firstnames ORDER BY RAND() LIMIT 1)
This query will pretty much use a static (one row) subset of the firstnames table to be joined with every row in addr_contacts, just like any ordinary join does, whereas your approach needs to execute once per row in addr_contacts.
If you want to find out exactly why this is happening, try MySQL forums, or even better, if you have access to Orcale support, use it. It would be interesting to get an exaplanation of what happens here.
I'd also recommend trying any other DBMS you might have access to, just to find out if results differ.
But, to speedily resolve the issue, create two querires. One selects all needed rows from addr_contacts, the other selects every single row from firstnames. Loop over firstnames and create an array of rows indexed from 0 to (N - 1), where N is the number of rows in firstnames.
Then, as you fetch each row from the addr_contacts result set, you create a random number between 0 and (N - 1) and add the value from that row index in your previously created array to the currently fetched row from the addr_contacts result set.