Compiling Python scripts (to .exe) that use ArcGIS Geoprocessing Tools?

First question: how much of this are you doing in Python? Are you just calling out to Geoprocessing tools or are you doing a significant amount of numeric analysis in Python? If the former, the bottlenecks likely live in the tools and using native code in your script won't buy you as much as some other clever workarounds. If the latter, then you may want to find what's slow and make it faster with better algorithms, or possibly numpy, or some other option as discussed below.

py2exe does not actually compile your code to native x86/x64, it just provides an executable that embeds your script as bytecode and provides a mostly portable way of distributing it to users without Python on their systems. It failed when attempting to bundle arcgisscripting, which is why it did not work. Actually getting py2exe working still won't do anything performance-wise.

I very strongly recommend you first use a profiler to identify the slow bits and optimize from there. There is a very good set built in to Python, use cProfile on a long run to find potential places to make it faster. From there you can optimize away sections into custom C or possibly experiment with small portions as Cython .pyx modules.

You can look into Cython for possibly building the whole Python script as a native code extension module, but Psyco may also give you an performance boost with a lower barrier to entry.

How long does the watershed delineation take if run from the standard tools in ArcToolbox as compared to the script version? If the times are similar, then I suspect that there will be no improvement. You might want to consider running long processes in the background outside of ArcMap.

Don't use a personal geodatabase without good reason. In our experience they are consistently much slower than all other forms of esri data storage (ref). Though I have read one report here on GIS.se that saw faster personal than file gdb.

When the workflow consists of many small iterations the call to create the geoprocessor and check out a license is often the most time expensive part of using python. So doing as much as you can either in front of or behind gp = ... (or import arcpy in v10) is one technique I use a lot.

With regard to compiling, this quote says it best:

It's worth noting that while running a compiled [python] script has a faster startup time (as it doesn't need to be compiled), it doesn't run any faster.

Mark Cederholm has a presentation about using ArcObjects in Python with some statistics on shapecopy operations (slide #4). Python doesn't fair very well, running at 32% of what can be achieved with C++ (VBA was 92%, VB & C# at 48%). Don't go running and screaming too quickly, many of the geoprocessing tools are python scripts anyway (search c:\program files\arcgis\ for '*.py').

As many have said in other venues, with python the time spent trying to optimize performance by compiling or writing a C or C++ core function often dwarfs any actual performance gains (possibly) made at runtime. Many say Python's chief benefit is optimizing and improving developer time; human attention is vastly more valuable and expensive than machine processing time.