Q:

how are user ids assigned to new users? 

what determines what user id to which a new user account will be assigned?  On my site, Drupal 7.37, new user accounts are assigned to non-sequential user ids.  All new users now have user ids well above 3500. 

A:

There are a couple of layers here...
Any code that calls user_save can technically affect what ID is assigned.  If the account object has a uid property, that is used, otherwise it comes from the database:
// Allow 'uid' to be set by the caller.  There is no danger of writing an
// existing user as drupal_write_record will do an INSERT. 
if (empty($account->uid)) {
  $account->uid = db_next_id(db_query('SELECT MAX(uid) FROM {users}')->fetchField());
}

So if an ID is provided, great, if not (which is the norm), it gets more complicated. 
The users table doesn't have an auto-increment column (probably because an ID of 0 is used for the anonymous user, and there's no way to support that across all DB platforms).  If you were to just get the last inserted user ID + 1, you're open to race conditions when other requests get the same ID returned before the first script has had a chance to insert the record into users. 
Because of that, the Sequence API is used.  The sequences table has a single, auto-incremented primary key column.  When a new, unique, identifier is required, a record is inserted into that table, and the auto-assigned ID is returned to Drupal.  That ensures it's not susceptible to race conditions, as the operation has already completed and any other requests would be guaranteed a new ID. 
If you just need to hack around the problem you mentioned, and you're not worried about or prepared to take the risk of race conditions, add this to a custom module:
function MYMODULE_user_presave(&$edit, $account, $category) {
  if (! empty($account->is_new)) {
    $account->uid = db_query('SELECT MAX(uid) FROM {users}')->fetchField() + 1;
  }
}

