The most important thing I would ask is who have you worked with and can I speak with your references. What their current and former clients say will speak volumes.

If I am clueless about my company brand, or branding in general, I would want to know from their clients how they felt about the firm's process in uncovering the current brand essence.

If I have a good handle on my company brand I would want to know how they enhanced their clients' current image and uncovered untapped elements of their brand drivers.