How about:

SELECT c.* --Replace with the desired column list

FROM

/* Get list of all valid BuildingId, UserId combinations. I

assume that these are separate tables that are linked with a foreign key.

Not knowing which is the Primary and which is the foreign key, I just added the JOIN.

You can probably replace that with a SELECT from the FK table. */

(SELECT BuildingId, UserId FROM BuildingTable INNER JOIN UserTable ON JoinColumnA = JoinColumnB) a

/* Using this list, get the MIN and MAX DateID of each valid BuildingId/UserId combination */

CROSS APPLY (SELECT MAX(DateID) AS MaxDate, MIN(DateID) AS MinDate

FROM myTable WHERE BuildingId = a.BuildingId AND UserID = a.UserId) b

/* SELF JOIN your source table using this data to filter results. */

INNER JOIN myTable c ON c.BuildingId = a.BuildingId AND c.UserID = a.UserID

AND (c.DateID = MinDate OR c.DateID = MaxDate)

On a similar table in my DB, I was able to get results in less than 1 second with cache, less than 10 seconds after a DBCC DROPCLEANBUFFERS statement.

It was retrieving the first and last row for each "UserId/BuildingId" (Not UserId/BuildingId for me, but something similar) combination in a table of 23 million rows, with 6500 rows in the results.