Do I have to request permission from a website to use an image that they use to promote their product on their site? I am currently checking proofs for a Springer article. The editor has asked us to provide permission details for all figures.

One of the figures is a screenshot from a software product, as found in the front page of the product's website. We use it to exemplify typical interfaces found in these types of products, and cite the site that it was taken from. With a bit of work we could re-generate the same image by downloading the product (its free, but supported by a for-profit company) and adding in sample data.

Since the screenshot is promotional material by the company, must I contact the company to request permission to use it in our paper, given that attribution is already correct, or can I already claim fair use due to its status as "promotional"? Re-creating the screenshot would also rely on fair use, according to this answer.
It doesn't matter if the material is promotional or not. It doesn't matter if the material is freely available or not. What matters is copyright. You have to ask if you want to use copyrighted material.

On a different note, the company may really be unhappy if you use a screenshot which might be of bad quality (at least it's a pixel image) instead of a high quality, tailor made (possibly vector graphics) image for that purpose.