If you relax the constraint that the Position column must contain integers from 1 to N and instead allow it to contain any numbers then you can do both searches and updates efficiently.
You can insert an item between two other items with position A and B by calculating the average (A + B) DIV 2. For example if A is 10000 and B is 12000 then your new position is 11000. Occasionally you will run out of gaps due to clustering, at which point you can run through the whole table redistributing the positions more evenly.