Нам в этом поможет мега бибизян по имени Greasemonkey, который живёт в зоопарке под названием FireFox.

Если у Вас ещё не установлен FireFox и Greasemonkey, то навёрстываем упущенное.

А те кто с этим уже справился, устанавливают вот этотскрипт. Затем переходите на страничку http://vkontakte.ru/wall.php и идёте пить чай. Больше никаких действий от Вас не понадобится. После того как все сообщения будут удалены, скрипт так же можно удалить, он вам не понадобится до следующей уборки.

ЧИТАТЬ ОБЯЗАТЕЛЬНО: А теперь чуточку внимания. Если у вас включен Greasemonkey и установлен скрипт для очистки стены, то при каждом посещении адреса http://vkontakte.ru/wall.php или http://vkontakte.ru/wall.php?id=[ваш id] будет начинаться автоматическая очистка сообщений со стены. Поэтому после запланированной чистки, надо удалять скрипт, чтобы случайно опять чего не почистить. Это мой первый скрипт для Greasemonkey, посему знаю ещё не все его возможности, вполне возможно что он будет дорабатываться и начало операции можно будет подтвердить или отменить, но это потом и не факт
Удаление сообщений проходит не мгновенно, так как, при частом запросе к серверу, происходит блокировка страницы и некоторое время вам будут показывать http://vkontakte.ru/blank.php при обращении к странице стены, для предотвращения блокировки, между запросами к серверу установлен период ожидания в 1 секунду, а так же +2 секунды на каждую страницу, перед её повторным обновлением. Т.е. на очистку одной страницы с 20ю сообщениями приблизительно будет уходить (20*1)+2 секунды.
Приятного использования, если возникнут какие-то проблемы, то отписывайтесь в комментариях. При использовании данного скрипта на свой страх и риск, пользователи берут всю ответственность на себя
P.S. при написании скрипта, ни одна стена не пострадала.