ArcSDE (Spatial Database Environment) is a software product from ESRI which handles geographic databases. I like to think about it as another tier which wraps all the access to the geographic features that are stored in the database. When you want to access some geographic data, SDE generates queries which access the geographic tables and retrieves the data.

After this very short intro, a question raises: How do know which queries and which operations SDE performs on the database?
This is critical when you have unexpected behavior in your application which you suspect originates in the database.

Luckily SDE has a Debug Mode. In this mode SDE writes all the operations it performs to log files. Shani helped me find some information about this mode. More on how to initiate the mode (SDEVERBOSE & SDEINTERCEPT): English, Herbrew

Recommendations

Recreate the issue in a smaller scale

Before enabling this mode, first try to create a simple program that recreates the problem as simply as possible (In my case a spatial query which get halts at some point and is being timed out).
Only then enable this mode so you will have the exact information in the log.
This way you wouldn't need to dig the logs (which can contains couple hundred rows) for the information you need.

SDEVERBOSE and SDEINTERCEPT should be initiated together

Initiate both modes at once (SDEVERBOSE & SDEINTERCEPT), so you will have the maximum information required.
SDEVERBOSE triggers an accumulating log for all the operations that are being performed by SDE.

SDEINTERCEPT creates a log file for each operation (or transaction) that is being performed, so every operation has a different log file (the order of the operations is described by the extension of the log files: .001,.002,*.003 and so forth)

Turn on for a single operation

Perform the operation that causes you trouble and then turn the mode off: This is because the logs rapidly grows (In my case the mode has been turn on for about 30 minutes and the logs exceeded 120MB).

Log file names

In ArcSDE 9.1/9.2 the name if the SDEVERBOSE log file is "sde_esri_sde.log" and not "sde.errlog".

Logs are erased when SDE is restarted

Remember that when you restart the SDE service the logs are erased. So before restarting copy them to somewhere else not in etc directory.
You can change this behavior by setting an environment variable called SDELOGAPPEND to TRUE (for Unix only).

One more thing: There is another log file which is called giomgr_sde.log. This log contains information about the processes that are managed by SDE and can also be used for understanding the problem.

Let the bug hunt begin...