A few things:

Eliminate the middle men. Who do the small/medium datacenters use to build their custom hosting hardware? It's likely someone like Ma Labs where you get quite a savings over Amazon/Newegg, particularly when you buy components for many servers at a time.

Pay in advance, when it makes sense and is possible. Talk to colo operators, you can likely get a better deal if you pay for 1/3 years up front.

When you build the hardware yourself, you can do things no operator can do for you... tailor it exactly for your own domain needs.

Analyzing your domain needs to define server roles that you might need (e.g. load balancer, app server, relational database, hadoop cluster, nosql database, key/value stores like redis, etc) will lead you to commonalities in hardware/components needs. Now you can develop a few physical server types, order in bulk, and not have to keep so many spare components on hand.

For us, we are able to split out our datacenters by "critical"/"non-critical" for huge cost savings. Our "critical" datacenters host traditional production level servers. Things that MUST have up times of four/five nines. We can get 50Mbps 95th percentile, quarter rack, 10 amp for roughly $400 a month. These are great, but you have to make the most of each U.

We do a lot of machine learning, map/reduce, and general processing. The app needs this, but because I coded for it... if the uptime is, say, 99% and not 99.9999% it has VERY little impact on our end users (think of these as worker dynos). Now, I can have a whole rack here at the office able to handle for 90% of outages without issue. The nice thing about this is, I no longer have to make the most of each U. I can now build servers completely different than I would in a traditional datacenter. It also comes with little added expense to our normal operations (add redundant internet, networking, UPSes, and insurance). I can build a 1u, 25 ECU-equiv, 32GB, SSD based server for ~1.1k. Fill the rack! :)