First off, if you want your code at all portable, do not use REPLACE. It is mysql specific (as far as I know).

Next, indexes are great. Try EXPLAINing your queries. That will give you a clue on what is going down.

Finally, make a function to check if the id exists and memioze it. This is essentially creating a perl cache, but it is transparent to you.