The Magento message is only a notification. Magento doesn't have any function to detect whether it has been patched or not. You make it go away by going to System=>Notifications and mark the notification as being read.
The only way you can tell is the append to app/etc/installed.patches.list tells you if the patch had been run and by actually diff'ing the patched files against your version's unpatched files to see that the changes have been applied. (Download the install archive, uncompress somewhere so you have originals)
Ask the hosting provider how they've determined the patch hasn't been installed.
I don't trust that grep command that was posted, I came across it, tried it and it kind of did nothing.
The following command line entry can quickly tell if this file has been patched by looking for the added _internallyForwarded flag. Run it in your Magento root folder:
grep "_internallyForwarded" app/code/core/Mage/Core/Controller/Request/Http.php
The following output is what you would expect to show the file has been patched.
public_html$ grep "_internallyForwarded" app/code/core/Mage/Core/Controller/Request/Http.php
protected $_internallyForwarded = false;
$this->_internallyForwarded = (bool)$flag;
return $this->_internallyForwarded;
