I've successfully resolved this by wrapping the pair of queries in a transaction. Not as optimal as I had hoped, but at least it has appeared to stop the race condition. It does appear to have increased my server load a bit, but I'm still investigating whether it was this or something else.

Just as a follow-up, using this method I am now getting deadlocks, so it did not solve the issue.

I have created a package that gives a trait you can apply to your models and have REPLACE and INSERT IGNORE queries. It's really just a macro but it saves the challenge of having to build a raw query and its bindings every time you need it.

https://packagist.org/packages/jdavidbakr/replaceable-model