[sql-server] Cause of a process being a deadlock victim

I have a process with a Select which takes a long time to finish, on the order of 5 to 10 minutes.
I am currently not using NOLOCK as a hint to the MS SQL database engine.
At the same time we have another process doing updates and inserts into the same database and same tables.
The first process has started, recently to end prematurely with a message

SQLEXCEPTION: Transaction was deadlocked on lock resources with another process and has been chosen as the deadlock victim.

This first process is running at other sites in identical conditions but with smaller databases and thus the select statement in question takes a much shorter period of time (on the order of 30 seconds or so). In these other sites, I don't get the deadlock message in these other sites. I also did not get this message at the site that is having the problem initially, but, I assume, as the database has grown, I believe I must have crossed some threshold. Here are my questions:

1. Could the time it takes for a transaction to execute make the associated process more likely to be flagged as a deadlock victim.
2. If I execute the select with a NOLOCK hint, will this remove the problem?
3. I suspect that a datetime field that is checked as part of the WHERE clause in the select statement is causing the slow lookup time. Can I create an index based on this field? Is it advisable?

Although @Remus Rusanu's is already an excelent answer, in case one is looking forward a better insight on SQL Server's Deadlock causes and trace strategies, I would suggest you to read Brad McGehee's How to Track Down Deadlocks Using SQL Server 2005 Profiler

Here is how this particular deadlock problem actually occurred and how it was actually resolved. This is a fairly active database with 130K transactions occurring daily. The indexes in the tables in this database were originally clustered. The client requested us to make the indexes nonclustered. As soon as we did, the deadlocking began. When we reestablished the indexes as clustered, the deadlocking stopped.

The answers here are worth a try, but you should also review your code. Specifically have a read of Polyfun's answer here: How to get rid of deadlock in a SQL Server 2005 and C# application?

It explains the concurrency issue, and how the usage of "with (updlock)" in your queries might correct your deadlock situation - depending really on exactly what your code is doing. If your code does follow this pattern, this is likely a better fix to make, before resorting to dirty reads, etc.