You could use "disallow concurrent execution" in combination with the before commit microflow mentioned by Michel to prevent concurrency problems. Upon concurrent execution you could execute a microflow which will sleep for a while and then tries again. This will go on until it succeeds.
Microflow aggregate functions are optimized automatically if the variable resulting from the retrieve activity used as input for the aggregate function is not used elsewhere in the microflow. So instead of retrieving a list and counting the number of objects an SQL COUNT(), MAX(), .., function is called directly in this case.
UPDATE (in response to UPDATE 2 and 3)
What I would do is a make an "ObjectBeforeCommit" microflow in which the sequence number is incremented and set "disallow concurrent exeuction" to false. When you tick "disallow concurrent execution" you can choose to display an error message or to execute a microflow when an attempt for concurrent execution is encountered.
For this particular case I would choose to execute a microflow which will sleep for a while (e.g. by calling a java action which calls Thread.sleep() ) and then call the "ObjectBeforeCommit" microflow again. This process will continue until it succeeds.
In the before commit microflow you should check whether the object is new (with the isNew() function call in microflow expression). This will return true if the object has been created but not yet committed. In that case the sequence number should be incremented, otherwise nothing has to be done.
I think creating sequential numbers is not the intention of autonumbers. However a solution to your problem might be using an attribute which is set in the before commit to the total number of objects. (which, when all number are sequential and start at zero, equals the highest number + 1)
Another solution is to use the max aggregate function, and add 1 to it.
I do not dare to say what will happen in your case when two concurrent users commit an object at the same time.
Concerning the second question; max and count are translated and executed at the database level, so the performance penalty is not that bad; the runtime does not retrieve and instantiate all objects to calculate aggregates.
(i will notify the r&d guys on the question)
If you want an unbroken sequence you should generate the number when nothing can fail, so not on create but with an update doing just the number generation.
You need some kind of locking to ensure unique numbers and to only give out the next number when the current is committed. I don't know how to lock tables/records in Mendix.