As far as the label making thing, and actually all of it, these people don't even know what it is they want(and change their minds every 30 seconds anyway). When they mentioned the label making thing in their last list of demands I asked what label making software they are currently using and apparently that would be none which is why they expect their shopping cart to do it for them I guess.
As far as the search engine thing goes this is kind of a unique project where search engines aren't actually an issue. The store exists almost soley for customers who have moved out of the company's distribution area and want the product shipped to them.
I will look at cartit. Thanks for the suggestion! I've looked at about a dozen so far but I'm not finding anything which will create an invoice or shipping label for them. Do I just need to get them to buy other software which will be compatible with whatever shopping cart they decide on to handle these tasks? If so, suggestions on that?