Tuning An UPDATE Statement On A Large Data Set?

I'm updating the name data in a large user database with the following UPDATE statement. The staging table was bulk loaded from a flat file and contains 10 million records. The production table (Recipients) contains 15 million records. This worked correctly but this single update statement took an entire ten hours to run which is way too long. While it was running the server was clearly 100% disk bound. CPU activity was near nothing. We've just upgraded RAM from 1GB to 2GB but we expect data sizes to grow significantly and we can't keep adding RAM. Absolutely nothing else is running on this server. Any ideas how I can optimize this?

UPDATE Recipients
SET [First] = Stages.[First]
, [Last] = Stages.[Last]
FROM
Stages
INNER JOIN Recipients ON
(Stages.UserName = Recipients.UserName
AND Stages.DomainID = Recipients.DomainID)
WHERE
(CASE WHEN Stages.[First] IS NULL THEN 1 ELSE 0 END
+ CASE WHEN Stages.[Last] IS NULL THEN 1 ELSE 0 END)
<=
(CASE WHEN Recipients.[First] IS NULL THEN 1 ELSE 0 END
+ CASE WHEN Recipients.[Last] IS NULL THEN 1 ELSE 0 END)

Text execution plan. I've made small annotations with the % information from the graphical execution plan:

|--Clustered Index Update(OBJECT:([Recipients].[dbo].[Recipients].[PK_Recipients]), SET:([Recipients].[First]=[Stages].[First], [Recipients].[Last]=[Stages].[Last]))
|--Top(ROWCOUNT est 0)
|--Sort(DISTINCT ORDER BY:([Bmk1000] ASC))
14% |--Merge Join(Inner Join, MANY-TO-MANY MERGE:([Stages].[DomainID], [Stages].[UserName])=([Recipients].[DomainID], [Recipients].[UserName]), RESIDUAL:(([Recipients].[UserName]=[Stages].[UserName] AND [Recipients].[DomainID]=[Stages].[Domain
25% |--Clustered Index Scan(OBJECT:([Recipients].[dbo].[Stages].[IX_Stages]), ORDERED FORWARD)
61% |--Clustered Index Scan(OBJECT:([Recipients].[dbo].[Recipients].[PK_Recipients]), ORDERED FORWARD)

Everything I've heard on the subject suggests you change the index scans to index seeks. How do I do this?

Any other tuning advice is greatly appreciated.

Here are the exact statements I used to create the tables:

CREATE TABLE Recipients (
ID INT IDENTITY (1, 1) NOT NULL,
UserName VARCHAR (50) NOT NULL,
DomainID INT NOT NULL,
First VARCHAR (24) NULL,
Last VARCHAR (24) NULL,
StreetAddress VARCHAR (32) NULL,
City VARCHAR (24) NULL,
State VARCHAR (16) NULL,
Postal VARCHAR (10) NULL,
SourceID INT NULL,

CONSTRAINT PK_Recipients PRIMARY KEY CLUSTERED (DomainID, UserName)
)

CREATE TABLE Stages (
ID INT NULL,
UserName VARCHAR(50) NOT NULL,
DomainID INT NULL,
Domain VARCHAR(50) NOT NULL,
First VARCHAR(24) NULL,
Last VARCHAR(24) NULL,
StreetAddress VARCHAR(32) NULL,
City VARCHAR(24) NULL,
State VARCHAR(24) NULL,
Postal VARCHAR(10) NULL
)
CREATE CLUSTERED INDEX IX_Stages ON Stages (DomainID, UserName)