Hi Joel,
Yes, you need Pro for this, and maybe BCSE's X-mall might be a good idea:
http://www.bcsengineering.com/store/x-mall/
Pro is complicated, it doesn't always follow the logic you'd expect - for some people it works exactly how the want and expect - for others it makes no sense. Suggest having a good look at the demo, maybe install a copy and really examine how your customer wants it to work in terms of shipping, invoicing, searching, etc and really get into the fine detail of all this before you give them a cost and final solution - because if you get to the end and they suddenly say the want shipping to work "this way" and that's totally opposite to how it does work, then you've got a problem.
There are lots of Pro threads in here with some of the potential problems - familiarise yourself with some of those first as well, so you have an idea what might come out of the woodwork once you are too far into it.