That's definitely conflicting information. I have a Dell Vostro and a Sony Vaio. Both are laptops and both have Office Starter. I've used the recovery partition on both machines and both machines still had Office Starter when the recovery was finished. Perhaps this is a manufacturer's decision on whether or not Office Starter will be recovered.
Perhaps it would be worthwhile to make a System Image of your hard drive and save it on an external USB drive. That image would include everything that's installed, including Office Starter. Once you have the image, go ahead and restore your machine using the recovery partition. If Office Starter is not included, you'll know for sure that HP was correct and Microsoft was wrong. You could then restore your system image and be exactly the way you were when you made the system image including having Office Starter.