Похоже, ваш запрос использует неверный план запроса. Попробуйте установить ARITHABORT ON, и это должно обойти план запроса:
Dim arithabortCmd As New SqlCommand("SET ARITHABORT ON", cn)
arithabortCmd.ExecuteNonQuery()
Я бы удостоверился, что индексы базы данных обновлены, выполнив этот SQL в базе данных:
-- Execute this to rebuild all for a given database. Replace the <databasename> after EXEC.
EXEC <databasename>..sp_MSforeachtable @command1='DBCC DBREINDEX (''*'')', @replacechar='*'