Can't you just give the client a list of generated IDs on the first request and check if the IDs are from the pregenerated IDs afterwards? That should be a lot cheaper than checking all IDs you ever generated.
You can do that I suppose. But I have found that in most cases I have a unique index on the ID anyways, as they are often table primary keys. So really I just have to ensure that it is either an INSERT or an UPDATE to a record that is owned by the user.
Then you don't really have the problem this is about though, and which UUIDs are supposed to solve. The real pro of UUIDs is that you can issue them in distributed situations where you can't look up the already used IDs easily.
