I recently struggled with something similar. I ended up using GDAL. GDAL works great, is fast, and has configs for a number of different raster formats. I ended up deciding on using .IMG (the GDAL .IMG driver supports rasters >2 GB) and mixing in GDAL calls into my script. Depending on your programming environment & language, there may be (probably is?) a GDAL API for you.
I just upgraded to 10, and saw a reference on one of the ArcGIS blogs indicating that GDAL is pre-configured in the ArcGIS Python 2.6 implementation. I haven't messed around with that, and in the past have explicitly maintained a GDAL install on my ArcGIS Python 2.5.3 install. It sounds like you aren't programming in python, though, and may already be aware of the GDAL option.
I don't look to make it complicated, but GDAL was 10 - 50 x faster. Made the approach for feasible rather than infeasible...
