The issue ended up being a firewall problem. I found it accidentally, but maybe the steps I took will help someone else solve a similar problem:

I decided to try...

I was able to run huge queries through SQL*Plus from both my computer and our SQL Server box. This rules out a network issue and an issue with Oracle....

Thanks. That helped a lot. I won't try to justify the way I was going about it. I was obviously just thinking about it from the wrong...

That query took 12 seconds. That's a bit longer than I'd like it to take, but within the acceptable range. The execution plan looks like this:

The inner-most clustered...

Here is the actual execution plan:

For comparison, the WOStatus DELETE query, which takes significantly less time, looks like this:

The major difference appears to be the sorts on the index delete....

8 indexes including the primary key. The data space is 17.5G, and the index space is 7G.

There are no foreign keys.

Some additional information:

It stalled out while there was no...

...Or not.

The SELECT statements finish in a fraction of a second, but the DELETE statements continue to stall out.

Wow, talk about not seeing the forest for the trees. All three queries finished instantly, each using a index seek. I've altered the DELETE statements, and I expect...

Well, your suggestion made me quickly realize that I was missing two indexes. The field "CloseDate" was used often in queries, and was already indexed. The other two...

This is a critical issue that remains unresolved, therefore I must bump.

That's a fair point. I hadn't considered that.

I've actually revised the process such that the entire transaction occurs after the lookup. I still need to perform the lookup...

Nothing? What a bummer. It's almost impossible to troubleshoot these problems without an error message...

This really shouldn't be too much to ask for, should it?

All I'm getting from the profiler is that it's actually executing the stored procedure. Apparently BIDS is getting the field names by executing the script programmatically, and there doesn't...

Alright, I guess that's not working for stored procedures that run against another linked server. So I guess that solution won't work. Wonder how BIDS does it... maybe...