班石です

> しかし、一番いいのは「番号を使い切ることに意味は無い」と言い張ることで
> しょうね。

そうですけど、桁数を増やすことが出来ない、またはコストが高い場合は
難しいですね。

実際にデータを入れて実行してみました。
mysql> create table table2(a int);
Query OK, 0 rows affected (0.00 sec)

mysql> insert table2 values(1),(3),(4),(5),(8),(9);
Query OK, 6 rows affected (0.00 sec)
Records: 6  Duplicates: 0  Warnings: 0

mysql> select @i:=2,@x:=@i,@z:=@i;
+-------+--------+--------+
| @i:=2 | @x:=@i | @z:=@i |
+-------+--------+--------+
|     2 | 2      | 2      |
+-------+--------+--------+
1 row in set (0.00 sec)

mysql> select a,@x:=@x+1,if(a<>@x and @z=@i,@z:=@x,null) from table2
where a>@i
 order by a;
+------+----------+---------------------------------+
| a    | @x:=@x+1 | if(a<>@x and @z=@i,@z:=@x,null) |
+------+----------+---------------------------------+
|    3 |        3 | NULL                            |
|    4 |        4 | NULL                            |
|    5 |        5 | NULL                            |
|    8 |        6 | 6                               |
|    9 |        7 | NULL                            |
+------+----------+---------------------------------+
5 rows in set (0.00 sec)

mysql> select if(@z<>@i,@z,if(@x=@i,null,@x+1));
+-----------------------------------+
| if(@z<>@i,@z,if(@x=@i,null,@x+1)) |
+-----------------------------------+
| 6                                 |
+-----------------------------------+

 @i:=2の箇所で基準値を入れて下さい。
>昇順では２ならば６、
>６ならば７、７ならば１０をみつけるもの。降順では１０ならば７、
>７ならば６、６ならば２、２ならば０、０ならば該当なし、
はうまくいきました。