Qualified SEO specialists are hard to find. Those of us that have been in the game awhile, have our own businesses and clients.
Your best bet is to find someone that is willing to work with your company on a consulting basis.
Many of us have worked hard to build our own technology and techniques to obtain prominent rankings. Our work is protected on our own servers.
But, many would possibly be interested in helping your company set up an SEO marketing plan.
The problem you run into is:
(1) Your company most likely can't afford one of the top SEO individuals out there, to dedicate their efforts for just your company, working on-site.
(2) Do you really want to trust your SEO effort to an individual that fits your company's budget, but doesn't deliver? Especially, when results can't be gauged for up to 3-6 months?
I sympathize with your situation, but that's the bare facts.. A top notch SEO individual is most likely grossing over 100K annually in the US. Most are doing much better. I keep in touch with several in the business, but we never discuss revenues, so I can't verify that number I threw out.
Again, there are possibly some SEO specialists that may work on a consulting basis, with an hourly/project rate, and maybe bonuses based on increased traffic levels, corresponding to their efforts. That would be an option to investigate.
We are a unique breed, and rarely fit into a corporate environment structure.