Можно использовать готовую интеллектуальную капчу, которая появляется только для подозрительных пользователей.
Если пользователь не спамит - без капчи проходит.
Если вручную - то простейший способ - хранить в базе дату-время последнего сообщения с, как вы правильно заметили, useragent+IP, но я бы еще и сессию добавил.
Если очередное новое сообщение приедет слишком быстро - не пущать.