I see that the applications given in CUDA zone are of a scientific nature.

Is there, or has there been, anyone using CUDA to solve combinatorial optimization problems? If so, what problems have been addressed, what performance gains were reported and what problems were encountered during software development?

I did. I have big problems with branching (I have to make my program suffuciently less agile) and shared memory usage (I need to save 25x25 matrix what greatly reduced the number of threads which can execute in parallel) and performance gain was only 3x time faster than single-cpu implementation. I have dual core processor and so total speed factor was only 1.5. But I have 8600GTM with only 2 multiprocessors. If you have 8800 videocard with 8 multiprocessors, your chances are greater.