Had similar issues with reseeding "virgin tables". Key is that last_value in Sys.Idnetity_Columns is "null" for a virgin table, and not zero as one would have thought. The script below solved my issue:

declare @TableName nvarchar(123)

set @TableName = 'test'

IF NOT EXISTS(select *

FROM SYS.IDENTITY_COLUMNS

JOIN SYS.TABLES ON SYS.IDENTITY_COLUMNS.Object_ID = SYS.TABLES.Object_ID

WHERE SYS.TABLES.Name = @TableName AND SYS.IDENTITY_COLUMNS.Last_Value IS NULL)

DBCC CHECKIDENT (@TableName, RESEED, 0)