Resolví de esta manera:
La parte de config::set estaba mal, para acceder a la configuración de la base de datos debo usar el estilo punto (.), de esta forma:
Config::set("database.connections.sqlsrv.host", Crypt::decrypt($cliente->Server));
Config::set("database.connections.sqlsrv.database", $cliente->NomeDB);
Config::set("database.connections.sqlsrv.username", Crypt::decrypt($cliente->Username));
Config::set("database.connections.sqlsrv.password", Crypt::decrypt($cliente->Password));
Y luego vuelva a conectarse a la base de datos:
\Illuminate\Support\Facades\DB::reconnect();
Mi consejo para todos los que tienen este problema es usar una conexión de base de datos doble, una para la base de datos principal (base de datos del servidor) y otra para la base de datos del cliente. De esta manera puedes cambiar a ambos db, con este simple código:
Config::set("database.default", "sqlsrvCustomer");
\Illuminate\Support\Facades\DB::reconnect();
Con el primer comando puede elegir la base de datos del cliente y con el segundo puede conectarse a ella.