Fire your hourly rate.
The only way you'll ever make money with design is to become familiar with and accustomed to value-based pricing.
No client I've ever come across is willing to pay $150-$400 an hour... or willing to pay for 40 hours of work, at something ridiculous like $35/hr, when you've spent 30 hours of "rough" design exploration and only 10 hours actually finalizing something. However, most will gladly pay $600 without ever knowing it only took you 2 hours to design something.
When you start out.. that $600 may mean you only earn $10/hr because it took you 60 hours to finish a project... but as you improve your skill set and get better at estimating your time, you whittle that away and start making more and more money without really increasing prices.
Value-based pricing rewards you for being better at your job. The faster, more efficient you are, the more profit you make. Why should you charge an hourly rate clients will see as acceptable when you can do in 1 hour what other designers may need 5 hours to complete? Only value-based pricing is a viable model in my opinion.
So, in general, with value-based pricing in mind, yes you charge the client for your exploration time. But it's up to you to be quick about things. The longer you take, the less money you make -- which is a different mindset than "the longer you take the more the client pays". The client pays the price you've bid/quoted... you have to ensure you are A) bidding accurately and B) not eating your own profits by taking too much time with projects.
An example with value-based pricing:
A client approaches me for a tri-fold brochure. I know I can complete this in 3 hours tops... Client asks me what my hourly rate is. I simply tell then the cost for the brochure design will be $450.00.. the client is happy with that and hires me... It only takes me 2 hours to actually complete the brochure..... I make $450.00. ($225/hr)
Same client... different tri-fold. I tell them it's the same price, $450. They are happy and hire me. This time I ran into a hurdle and it took me 4 hours to complete... But those extra 2 hours I needed means I made less profit on this project compared to the previous one. I make $450.00 ($112.50/hr)
Same scenario if pricing were hourly:
Conversely.... the client approaches me and asks what my hourly rate is. I tell them its $150 an hour. They complain, whine, and balk. Telling me they generally only pay less than $40/hr. They expect to pay me the same rate they've paid others. As if every designer has the same abilities and skills.... but I'm not the same designer. So... lets pretend I cut my rate (which I NEVER would) to something like, say, $50/hr. Then I tell them it'll take 3 hours.. they are thrilled and hire me... It only takes me 2 hours... I bill the client for 2 hours.... I make $100.00
Second trifold hourly. I bid at $50/hr. Tell the client it will take 3 hours. I run into a problem and it takes me 4 hours. What do I do about that additional $50? Do I contact the client asking for more money than I quoted (bad practice) or do I eat that figure as well, meaning for 4 hours of work I only made $150, essentially only $37/hr. Either way I must upset the client and possibly lose their business or make far less than I estimated. Even in the best case scenario and the client is happy to pay for the additional hour without a problem... I make $200.
You tell me which is a better pricing model.
Dollar amounts are fictions and have no actual bearing on my pricing. These are examples only and should not be seen as pricing advice.
If you are billing hourly, you need to be honest and ethical and never pad your time. It's the only real way to remain in business and keep clients happy. If you are billing based on an agreed upon amount then the amount of time it takes you to complete something is largely irrelevant. Your'e being paid for your knowledge, experience as well as your skill, not just the time pushing a mouse around on a desk.
For something like a logo project, which you mention, first you must know your overhead costs (electricity, equipment, software, rent, heat, water, etc). Then you calculate the approximate time needed multiplied by your hourly overhead... this gives you a minimum amount. After you have the minimum, it's a matter of market trends, current market pricing, depth and scope of the project, your area of expertise, etc to calculate the profit amount on top of the minimum you've calculated. This ultimately leads to a solid figure to bid/quote.
If you bid/quote a solid figure, the client has no worries that you will be asking for more money, and generally there's much less issue with payment since it's understood from the beginning. And it's up to you to remain within the time you've bid. Any additional time means you eat that cost, not the client.
Other possibly helpful questions:
Which is the most honest or ethical way to bill, hourly or fixed price?
Am I supposed to be paid even though my work isn't used?
Is it common to demand deposit/retainer to avoid payment disputes?
Underestimated project: Do you charge the excess time?
Whose responsibility is to give budget for job: Freelancer or Client