You could use locking, using the AcquireLock or WaitForLock functions from the CommunityCommons module.
Making objects unique can be quite messy when dealing with concurrent execution. Wether this is by webservice calls or by multiple users logged in at the same time. There are multiple ways to dealing with this:
Prevent the creation by setting disallow concurrent execution on the fetch or create microflow. But the nasty thing here is that the lock on concurrent execution is only released when the whole subflow is done.
Another thing you could do is add a unique constraint on the key value on database level. But you cannot do this when running in the cloud.
So a third option would be to do some java where you somehow keep track of all concurrent keys that you are working with. Then you check if the key is present in that list if not retrieve the entity that you want to get based on the key value, if not present commit it and return it.
Did you set "Disallow concurrent execution" to true for this microflow? You can specify this in the microflow properties.