Run the SQL Server Profiler and include the Showplan Statistics XML Profile event. Run your query for the large case (>= 30,000 cars) and see what it does.
Depending on your version of SQL Server, you might try a MERGE (if on SQL 2008 or higher), or a LEFT JOIN WHERE Car_ID IS NULL like this:
INSERT INTO CARS (CAR_ID, CARNAME)
SELECT C.CAR_ID, C.CARNAME
FROM @CARS C
LEFT JOIN Cars ON Cars.CAR_ID = C.CAR_ID
WHERE Cars.Car_ID IS NULL -- the car does not already exist
Also, you could try declaring the CarType to have a PRIMARY KEY of CAR_ID.
(I am assuming the TVP CarType key is CAR_ID and not CARID as you wrote. Also, you declared this table as USERS instead of CARS.)