These mistakes are avoidable with vision and a long-term plan; that long-term plan should be cloud. Public, private, hybrid is non-consequential; the goal should be cloud. Think of cloud as my colleague Jason describes it: "IT nirvana." That's all it is, whether the industry changes cloud's name next week and cloud becomes (or arguably already is) a bad joke, you're still shooting for nirvana. Your end goal is now: a flexible pool of IT resources that can be provisioned and de-provisioned on the fly, accessed from anything, anywhere, anytime, and has the ability to monitor who uses what--that's nirvana.
Plan for that regardless of whether you feel your organization needs or can budget for every piece of a private cloud or can move every application and service to a public cloud. This provides for a strategic growth path that allows day-to-day decisions to be mapped to a long-term goal. This same rule applies to data centers of all sizes and types. While a fully orchestrated data center might not be in the cards for every data center, there is no harm in designing for that as a long-term goal and ensuring appropriate flexibility and efficiencies are accounted for at each layer.
For infrastructure, data and services you choose to keep in-house, you'll move toward private cloud. In general terms, building a cloud from an infrastructure perspective requires you move through four stages: consolidation, virtualization, automation and orchestration. While these are arguable and differ by model, they are a common approach. These steps can be followed in stages building one layer upon the last with the end result being private cloud. If they cloud isn't in your plan/budget, you haven't lost anything; rather, you've gained the efficiencies of each layer and advanced, that much closer to nirvana.
With private cloud PaaS solutions and public cloud end goals, you'll be focused on the applications and data. From an application perspective, cloud requires far greater abstraction from the "single server, single, OS, single application" model that exists in both virtual and physical environments today. Cloud promotes designs that can be distributed and load-balanced, and that can support higher latencies where possible. Both the application and the data it uses/generates must be designed for greater flexibility. If your application teams have this as an end goal and your organization never fully moves to cloud, you still end up with a more agile application environment designed for today's computing demands.
With cloud as the vision and a road map in place, your computing environment can only improve. Design for nirvana and execute in stages, migrating your organization closer to cloud deployment models.