Yes, enthalpic gains usually mean entropic losses. The challenge is to find enthalpic contributions that are stronger than the entropic losses, or to find other ways of tying the entropic losses into the structure of your inhibitor rather than in the inhibitor-enzyme interaction.
One example of this that drives the molecular modelers nuts is the structured water molecules. These are water molecules which are hydrogen bonded into the binding site of the enzyme. If your molecular modeling program is not sophisticated enough to handle these water molecules, it can appear that simply adding a hydrogen bond donor (for example) to your molecule to reach a previously unused hydrogen bond acceptor on the enzyme would be a great way to pick up activity. In many cases, however, what you gain in enthalpy by adding the hydrogen bond donor to your inhibitor is lost by breaking the hydrogen bond to water, and the additional entropy kills you.
There are ways to make entropy work for you. If you can build the appropriate geometry into your inhibitor by using ring systems or stereochemistry to fix two sites of interaction into exactly the right geometry, then that entropy becomes part of the formation of the inhibitor and you don't have to make up for it when binding your inhibitor into the enzyme, as a floppier inhibitor with more degrees of freedom would.
Of course, the really strong enthalpic contributors would be those that actually make chemical bonds to the enzyme (irreversible inhibitors), but it is difficult to work in the appropriate amounts of chemical stability and selectivity into these types of molecules and many drug discovery programs avoid them. I would say "avoid them like the plague", but that wouldn't account for those drug discovery programs that are actually working on the plague and still wouldn't consider an irreversible inhibitor.