(sql server 2005)
I did have a varchar(500) that was indexed and was searched by a stored procedure

where thevarcharcolumn like '%' + @keyword + '%'

Which all worked fine, but now i need to up the character limit to 1000, however when i try and change the column to varchar(1000) and add an index it complains about the index size being greater than 900k

What datatype should i use to
a) let me store up to 1000 characters
b) keep the good performance i have with varchar(500)

I've read about varchar(max) and there seems to be quite a performance hit in using this.