It's time to think outside of the box
Target Web Designers, for example.
When a web designer recommends someone, their reputation is on the line. You, the web host, must be held to a higher standard, as you've got more than your own reputation on the line. Reinforce this message regularly.
Everyone loves affiliate programs, right? Pretty much all the big box places offer a 10% affiliate or something similar when someone signs up.
Now, instead of going with ****, which gives affiliates 10% of $48 ($4/mo * 12 = $48), charge the users $10 or $15 - what it actually costs to run a budget account. Now it's 10% of $120 or $180. Your developers are now getting the following:
$48 = $4.80
$100 = $12
$150 = $18
So, instantly, they're getting more of a kickback. And if that user is on a higher plan, the payout is higher, too.
But wait, there's more!
Web designers generally work with clients for the long term, some for more than a decade. So, instead of 10% of the first year, make the commission recurring annually. And don't be stingy—after all, they've done all the marketing for you to get the client—pay them commission on upgrades, too!
So, the e-commerce account that started out at $10/month is doing better and now needs a larger account at $24 or $34/month. Reward that designer for sending you a high-quality client!
All of the above is how I operated Hands-on Web Hosting. But let's go a step further—don't lock users into one-year contracts, and don't pay commission only once per year.
Set a reasonable payout level at $50. Generate the 10% commission, and when the user reaches $50, they can cash out.
Now, you're not losing any money on commissions! So many fear the commission, as you pay out after 60 or 90 days, then the client cancels, and you're left holding the bag. If the commission is paid monthly and kept on hold until they request a payout after $50, then the payout is strictly from income.
If you want, give a signup bonus of $20 when they join the program - that helps them meet their initial payout level faster, but it still encourages them to send at least 3 or 4 customers just to get the payout.
Don't be stingy - pay commission on reseller accounts too, on a VPS, and on dedicated servers. Pay them. They've been busting their ass marketing for you while you took care of support and awesome servers.
You just have to think differently than the mega-million dollar companies. Find the niche and go after it, be it web designers, podcasters, e-commerce platforms, local meetups, agencies, etc - there are plenty of places that have clients that need hosting. You need to market to them, and they'll do all the work for you!
Maybe this needs its own thread