Make the process simple
At our place we have the sets of software: standard software on every machine (browser, email, word processor etc.), standard software that can be requested (like... Mindmanager, some development tools, takes about two business days, on average) and non-standard software (anything you want to request, can take a long time depending on how expensive licenses are, what IT security says, if anybody else is using it already,...)
Yes, I would like it to be faster at times, but it works well enough. And I use mostly non-standard stuff for my work.