The code has been made thread-safe. We have done bulk record import testing across Dynamics CRM Online (v8.2 and v9.0) as well as on-premise and no duplicate record was created.
No, you have the option to generate Auto-Number even with random characters and date time-stamp. Having sequence number in generated auto-number is optional.
Sure, auto-number can be generated even for existing records. Refer knowledge base for instructions.
Yes, auto-number can be configured across multiple fields in an entity.