Если на сайте присутствует авторизация юзера через ВК - то можно через wall.search по определенной метке найти пост, передавая токен юзера. Если такого поста нет - значит не запостил, если есть - соответственно запостил. Можно еще через wall.get, сравнивая последние несколько постов с тем, который нужен.
Если авторизации нет и у юзера закрыт профиль - то никак. Если открыт - тогда нужно знать его id и передавать в этих запросах специальным параметром.