Would a sequential guid work in place of an int?

It should be less of problematic and it doesn't necessarily need to be the primary key (it could be a unique key and used as a foreign key as well).

http://sqlblogcasts.com/blogs/martinbell/archive/2009/05/25/GUID-Ordering-in-SQL-Server.aspx

http://developmenttips.blogspot.com/2008/03/generate-sequential-guids-for-sql.html