"Unrelated" INSERT and UPDATE blocking each other
Lets take a look on the execution plans.

1st query - Insert

BEGIN TRANSACTION;
INSERT INTO test (mykey, exp_date) VALUES ('B', NULL);


And its execution plan 

We see that sql server is doing Clustered Index Insert operation.

Now lets take a look on update

BEGIN TRANSACTION;
UPDATE test 
SET exp_date = GETDATE() 
WHERE exp_date IS NULL AND mykey = 'A' -- &lt;-- Blocking


And its execution plan

SQL Server scans the Clustered Index of the table, and put U lock on it, even if it can choose another index to find the matching rows. The reason is, because we have only 1 row in the table, and SQL Server Optimizer find easier to scan the Clustered Index instead of searching data in the non-clustered index.

But what if we force the sql server to use non-clustered index?

BEGIN TRANSACTION;
UPDATE test 
SET exp_date = GETDATE() 
FROM test WITH(INDEX = not_expired_keys)
WHERE exp_date IS NULL AND mykey = 'A' -- &lt;-- No Blocking!!!


And its execution plan

I think if we put more rows in the table SQL Server will choose the non-clustered index for finding the rows that must be updated, and there will be no blocking.