Optimizing an audit table for inserts and deletes

Question

I'm trying to identify the best way to design a table for audit purposes. Basically I log several last events for many users in one table. There's a limit on the number of records for each user. The new records come, the older go.

Something like this:

CREATE TABLE Audit
(
  UserId INT NOT NULL,
  EventId INT NOT NULL,
  CreationDate DATETIME NOT NULL,
  UpdateDate DATETIME NULL,
  -- Other data fields
)

The question is what to do with indexes. I'm thinking of creating the clustered index on (UserId, EventId). But since user activity happens independently it would mean inserts in the middle of the table and deletes in the middle of the table. Probably not good.

Another thought is to add an artificial AuditId field just to have new records get increasing numbers. Like this:

CREATE TABLE Audit
(
  Id INT, -- Becomes the clustered index
  -- The same as above
)

This way new audit entries will be appended to the end but deletes will still happen in the middle of the table. It's probably better than the first option but I'm not sure.

This table will be used frequently, basically every user activity is going to be logged (1 insert) and the oldest activity gets deleted in the same transaction (1 delete). This needs to be fast. Well, I want it to be instantaneous ideally and not noticeable performance-wise.

I also need to be able to retrieve the set of records for a particular user quickly. It can probably be covered by a non-clustered index.

I'm asking for advice in designing this table for optimal performance.

EDIT: I think I have missed something important to mention.

What I'm trying to track is not instantaneous in time but rather a period in time. There are several places in the system where I need this. Consider what the user is doing an activity of some sort that may span some period of time. If certain conditions are met then an existing activity is reused (refreshed, updated). I only wish to delete older sort of abandoned activities. For example, within 2 weeks one user may have issued like 50 of activities, but for another user to produce than many may take over a year. That's why I don't want a generally ordered log for all users together.

It is also not clear how should I cluster per datetime (as suggested). Do I do it on initial creation event or on the update event?