Having two accounts on a device is a real hassle. Until it makes sense for the company to get a Dunn & Broadstreet number and go enterprise, the gifting of apps is the easiest way to go.
If the app allows them to perform a critical job function, how is even $500 a year "expensive" when you are paying a salary, benefits, insurance. I don't mean to trivialize any IT expense, but would anyone want to work with a company that's so cheap, they won't pay for tools that make sense? Especially tools that let it's employees get work done 24/7 wherever they have a cell signal.
We're not talking about $25k which is a ballpark true costs of a 10 person laptop deployment covering one year and light software. If you look at this from a productivity / ROI standpoint - iOS deployments are some of the cheapest on the planet as well as the easiest to justify. Just buy apps that are obvious winners in the next 6 to 18 months and assume your employees will stick around.
That being said, most deployments I have seen end up layering a work Apple ID for work purchases and a personal Apple ID for personal purchases. At some point, people will be more comfortable expensing iOS app purchases like they expense hotel rooms and instead of worrying about losing all the purchases, they will learn that losing only a fraction of the apps when an employee leaves or changes roles isn't as expensive in practice as it seems when you start upon a project where all apps are purchased through Apple's app store ecosystem.