Aquí hay otra solución para hacer esto:
CREATE TABLE TEMP
(n int);
INSERT INTO Temp VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
SET @maxid = (SELECT MAX(orders_id) FROM orders);
SELECT s.id
FROM
(
SELECT id
FROM
(
SELECT t4.n * 1000 + t3.n * 100 + t2.n * 10 + t1.n + 1 AS id
FROM TEMP AS t1
CROSS JOIN TEMP AS t2
CROSS JOIN TEMP AS t3
CROSS JOIN TEMP AS t4
) t
WHERE id BETWEEN 1000 AND @maxid
) s
LEFT JOIN orders t ON s.id = t.`orders_id`
WHERE t.`orders_id` IS NULL;
Esto debería darte el orders_id s:
ID
1001
1002
1005
1006
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1021
1022
1023
1024
Demostración de SQL Fiddle
Tenga en cuenta que: Creé un TEMP tabla con valores de 0 a 9, para usarla para generar una tabla ancla que contenga valores de 1 a 10000 en lugar del bucle while que tenía en la consulta que publicó. Puede controlar los valores de esta tabla según los valores de su tabla. Si tuviera valores superiores a 10000 CROSS JOIN el TEMP mesa una vez más.
Actualización: Si el orders_id es del tipo de datos varchar simplemente cámbielo a INTEGER así:
SELECT s.id
FROM
(
SELECT id
FROM
(
SELECT t4.n * 1000 + t3.n * 100 + t2.n * 10 + t1.n + 1 AS id
FROM TEMP AS t1
CROSS JOIN TEMP AS t2
CROSS JOIN TEMP AS t3
CROSS JOIN TEMP AS t4
) t WHERE id between 1000 AND @maxid
) s
LEFT JOIN
(
SELECT CONVERT(orders_id, UNSIGNED INTEGER) AS orders_id
FROM orders
) t ON s.id = t.`orders_id`
WHERE t.`orders_id` IS NULL;
