How to design SQL schema that treats historical data as first-class citizen?
Trying to do FKs will just frustrate you - you don't actually need it.

If you handle versioning by using an InsertDateTime concept, then you're basically describing a Type2 dimension as used by many data warehouses. There is quite a lot of material out there about tuning systems that sit over the top of data warehouses, but from a T-SQL perspective, consider using APPLY. Like this:

SELECT ...
FROM ... AS t
CROSS APPLY (
    SELECT TOP (1) ...
    FROM ... AS rev
    WHERE rev.UID = t.UID
    AND rev.InsertDateTime &lt; @revdatetime
    ORDER BY rev.InsertDateTime DESC) AS something
WHERE something.IsDeleted = 'N'


This kind of construct benefits from an index on (IsDeleted, UID, InsertDateTime DESC). 

Alternatively, if you want to look at the whole table as at a particular time, use ROW_NUMBER() like:

WITH numbered AS
 (  SELECT *, ROW_NUMBER() OVER (PARTITION BY UID ORDER BY InsertDateTime DESC) AS rownum
    FROM ...
    WHERE InsertDateTime &lt; @revDateTime
),
VersionAtTime AS
(   SELECT *
    FROM numbered
    WHERE rownum = 1
    AND IsDeleted = 'N'
)
SELECT ...
FROM VersionAtTime
....


(edited from original to move the IsDeleted predicates outside the sub-queries, removing all versions at that particular time)