Generating a high number of unique random combinations

I have three tables: Users with an unique nickname, more than four hundred Names, 300000 plus Adjectives and a ton of possible combinations.

When subscribing, the user can generate an unique, random and hopefully funny nickname by combining a random name with a random adjective. The user clicks a button and Voilà! an exhilarating identity is born.

I select the random names and adjectives by running two queries for each:

SELECT FLOOR(RAND() * COUNT(*)) AS `offset` FROM names/adjectives

and

SELECT * FROM names/adjectives LIMIT offset, 1

Then I check if the User was unlucky enough to generate an already existing identity.

SELECT COUNT(nickname) FROM users WHERE nickname=:generatedNickname

If he was, the poor chap, I loop through this again until it settles on something untaken.

But, as you guys probably already figured out, the growth of the user base also means lengthier loops and more sweat from my feeble EC2 Tier 1 Matchbox. So I came up with a brilliant solution: What if I pre-generate all the possible combinations and stuff them in a huge table? This will allow a simple pluck and play operation while I'll be sipping worry free martinis on some anonymous beach or would I? Will my humble LAMP instance tremble and flee at the glorious sight of the humongous tables (both male and female)? Is there any better solution?