It's obviously not cryptographically secure, as in someone else could use the same algorithm to generate UUIDs that your system recognises, but could be a quick way of doing a verification before you hit the DB.
You'd have to trade that DB lookup with CPU cycles for a signature validation.
For example you can use HMAC.
You send the UUID and HMAC-of-UUID to the client.
The client sends back UUID + HMAC-of-UUID.
You re-calculate HMAC-of-UUID-provided-by-client (using your secret key).
If the calculated HMAC matches the HMAC provided by the client you have confirmation that the UUID was issued by you. Because without the secret key the client can't calculate the correct HMAC for a random or modified UUID.
There are 124 bits available. (Actually a little less but let's pretend only 4 bits are needed for the version to keep it simple.)
You'll have to decide how many are the ID and how many are the signature. Let's say 32 bits are your ID and the remaining 92 are the signature. (Adjust according to your own needs.)
Let's suppose your ID is 1. Now you need to hash that ID together with a private key using an HMAC algorithm. This signature will have more than 92 bits so trim your signature to this length.
Now build your UUID by combining the 32 bits of your ID with the 92 bits of the signature and four bits specifying version 8 (proprietary).
To test if a claimed UUID is yours, pull out the 32 bits of ID and repeat the process of signature and building a complete UUID. If the bits match, success! If not, its a fake UUID.
Now read the responses to this comment to find out why you shouldn't do this.
The filter needs to be stored somewhere, so if your workload is write-heavy you'd be replacing lookups with updates, but if it's read-heavy most DB lookups can be replaced with filter lookups.