The last time I ran into a similar thing I solved this race condition by not erroring out on an invalid lookup until a reasonable number of seconds to allow the backend to catch up.