Personally I'll talk to my most trusted colleagues, and just talk about some crazy ideas, perhaps laughing at a lot of them. There's a lot of subsequent, 'Well obviously that's not going to work, but how about if you...' There might then be a bit of trying things out, perhaps reviewing what anyone else has done where they may be doing something similar in concept for a small part of their project (we never seem to have that much overlap!). It would proceed from there with tighter iterations of the above, a bit more discussion, which might just be a few words which could spark a new way forward. Then it's polishing, and assessment of the different routes that could be taken and which seems optimal for the job in hand.

It's not scientific but seems to get good results for us anyway. Like Ben says, it's hard to estimate how long it might take, but going through the process definitely results in a good robust solution, long term.