I actually extend my research time into client time and try to get them involved in the process. I'll usually start by talking with the client and try to create some sort of design brief. After I've got an understanding of what it is they actually want I'll prepare some documents that include a number of designs in styles similar to what they have expressed. This is when I like to sit down with the client and pick apart each of the designs with them and analyse the specifics so that I can better understand what it is they want and avoid that horrible situation of trying to guess at what they want me to do. This is especially helpful for clients who don't really know what they want!
Some times it doesn't work the first time and they end up not liking enough of the designs I've presented, which goes to highlight any possible issues there might be which need to be rectified. It also goes some way to building rapport with the client and there are many opportunities whilst discussing the designs to show your expertise and professionalism, this helps you to establish your credibility as a designer and to reassure the client that they are in safe hands!
Some clients are difficult and need many hours of research, but other times they have clearly communicated what they want and I am able to translate that instantly into a design style in a much shorter time. It does also depend on the type of project you're working on too. If you're in an art worker position such as Alex, you really don't get that level of flexibility because the priorities are completely different, it depends if your client is willing to pay for those extra hours or not, if they don't want to then it needs to be reflected in the amount of hours you are willing to put into their project!