I've had problems on very large databases with this. I think we were over
400,000,000 rows when we first noticed it. A reorganize would normally help.
Can you first run this query?
SELECT fulladdress FROM [dbo].[Addresses] WHERE FullAddress like
'%WARMINSTER%' and not like '% WARMINSTER %'
See if perhaps you are getting hits to Warministershireontheavon or
something like that. Note that most punctuation will be ignored.
If you are trully missing hits can you check the gatherer log to see if
there are any error messages?
Looking for a SQL Server replication book?
Looking for a FAQ on Indexing Services/SQL FTS