Задача состоит в следующем : необходим уникальный идентификатор для записи, чтобы можно было сортировать записи в порядке их добавления в таблицу. 
Например: все записи добавленные после записи с идентификатором "фыва352". 
Автоинкрементное поле не подойдет , т.к. записи могут удаляться. Делать выборку по времени - тоже не решение : за одну секунду можнт быть добавлено несколько записей. 
Есть какие-нибудь методы решения данной проблемы? Может можно как-то просто взять все записи после записи с данным ИД?

Автоинкремент как раз таки подойдет. Ну и что с того, что записи могут удаляться? Порядок их добавления при этом не изменится.

А что если тип "закончится"  (если часто удалять/добавлять записи)?

Сильно хочу посмотреть, как вы сумеете "закончить", например, bigint (8 байт) от –2^63 (-9,223,372,036,854,775,808) до 2^63-1 (9,223,372,036,854,775,807)   . Даже если удалять/добавлять по 1 000 000 000 000 (1 триллиону) записей в день, вам понадобится ~25 200 високосных лет.   

Если нужно только сортировать (а не, к примеру, синхронизировать несколько БД с независимо растущим автоинкрементом), то автоинкрементное поле - то что нужно. Помимо всего прочего, выборка с сортировкой по первичному ключу будет во много раз быстрее, чем по какому-нибудь GUID-у.

Спасибо, вообще-то, я так и сделал, но "заказчик" сказал, что это не лучший способ и разумней использовать рандомное число(но не сказал как потом выборку делать).

Прога создает каждый день докменты(грубо говоря), каждый из них должен иметь уникальный идентификатор(UID) на протяжении суток(рабочего дня). На следующий день можно начинать нумерацию заново по тем же диапазонам чисел. В данный момент у меня счетчик записывает номер последнего обработанного 'документа' в ini-файле. Как удобнее реализовать функцию сброса счетчика в начальное состояние(скажем, к значению равному единице)?