Sharepoint 2010, Can not delete file.

I`m having a trouble with deleting files. I can add new files or update files and database size is getting larger.
DB is not FULL and log size OK.

Checked the logs for the correlation. Here is the result from ulsviewer.

System.Data.SqlClient.SqlException: A severe error occurred on the current command.  The results, if any, should be discarded.  A severe error occurred on the current command.  The results, if any, should be discarded.    
 at System.Data.SqlClient.SqlConnection.OnError(SqlException exception, Boolean breakConnection)    
 at System.Data.SqlClient.TdsParser.ThrowExceptionAndWarning(TdsParserStateObject stateObj)    
 at System.Data.SqlClient.TdsParser.Run(RunBehavior runBehavior, SqlCommand cmdHandler, SqlDataReader dataStream, BulkCopySimpleResultSet bulkCopyHandler, TdsParserStateObject stateObj)    
 at System.Data.SqlClient.SqlDataReader.ConsumeMetaData()    
 at System.Data.SqlClient.SqlDataReader.get_MetaData()    
 at System.Data.SqlClient.SqlCommand.FinishExecuteReader(SqlDataReader ds, RunBehavior runBehavior, String resetOptionsString)    
 at System.Data.SqlClient.SqlCommand.RunExecuteReaderTds(CommandBehavior cmdBehavior, RunBehavior runBehavior, Boolean returnStream, Boolean async)    
 at System.Data.SqlClient.SqlCommand.RunExecuteReader(CommandBehavior cmdBehavior, RunBehavior runBehavior, Boolean returnStream, String method, DbAsyncResult result)    
 at System.Data.SqlClient.SqlCommand.RunExecuteReader(CommandBehavior cmdBehavior, RunBehavior runBehavior, Boolean returnStream, String method)    
 at System.Data.SqlClient.SqlCommand.ExecuteReader(CommandBehavior behavior, String method)    
 at System.Data.SqlClient.SqlCommand.ExecuteReader(CommandBehavior behavior)    
 at Microsoft.SharePoint.Utilities.SqlSession.ExecuteReader(SqlCommand command, CommandBehavior behavior, SqlQueryData monitoringData, Boolean retryForDeadLock)

Unknown SQL Exception 0 occurred. Additional error information from SQL Server is included below.  A severe error occurred on the current command.  The results, if any, should be discarded.  A severe error occurred on the current command.  The results, if any, should be discarded.

SqlCommand: 'DECLARE @@iRet int;SET @@iRet = 0;BEGIN TRAN EXEC @@iRet = proc_DeleteUrl @wssp0, @wssp1, @wssp2, @wssp3, @wssp4, @wssp5, @wssp6, @wssp7, @wssp8, @wssp9, @wssp10, @wssp11, @wssp12, @wssp13, @wssp14 OUTPUT, @wssp15 OUTPUT;;IF @@iRet = 0 BEGIN  EXEC @@iRet = proc_EnsureTranLockNotRequired @wssp16, @wssp17, @wssp18; END;IF @@iRet = 0 COMMIT ELSE ROLLBACK;SET @wssp19= @@iRet;'     CommandType: Text CommandTimeout: 0     Parameter: '@wssp0' Type: UniqueIdentifier Size: 0 Direction: Input Value: 'b4ad4689-5d9a-49c0-9862-977824df2ca6'     Parameter: '@wssp1' Type: UniqueIdentifier Size: 0 Direction: Input Value: '4f93e81a-4942-4547-ba0b-a1b64db3ff09'     Parameter: '@wssp2' Type: NVarChar Size: 4000 Direction: Input Value: 'sharedservices/it/MIS Documents/Copy of Crash timeline.xlsx'     Parameter: '@wssp3' Type: Int Size: 0 Direction: Input Value: '397'     Parameter: '@wssp4' Type: Bit Size: 0 Direction: Input Value: 'True'     Parameter: '@wssp5' Type: Bit Size: 0 Direction: Input Value: 'False'     Parameter: '@wssp6' Type: Bit Size: 0 Direction: Input Value: 'True'     Parameter: '@wssp7' Type: TinyInt Size: 1 Direction: Input Value: '0'     Parameter: '@wssp8' Type: Int Size: 0 Direction: Input Value: '3'     Parameter: '@wssp9' Type: Bit Size: 0 Direction: Input Value: 'False'     Parameter: '@wssp10' Type: Bit Size: 0 Direction: Input Value: 'False'     Parameter: '@wssp11' Type: Int Size: 0 Direction: Input Value: '4'     Parameter: '@wssp12' Type: Int Size: 0 Direction: Input Value: '0'     Parameter: '@wssp13' Type: Bit Size: 0 Direction: Input Value: 'True'     Parameter: '@wssp14' Type: NVarChar Size: 520 Direction: Output Value: ''     Parameter: '@wssp15' Type: UniqueIdentifier Size: 0 Direction: Output Value: ''     Parameter: '@wssp16' Type: UniqueIdentifier Size: 0 Direction: Input Value: 'b4ad4689-5d9a-49c0-9862-977824df2ca6'     Parameter: '@wssp17' Type: UniqueIdentifier Size: 0 Direction: Input Value: 'd3b09288-1cc5-4acf-b52d-63a13adebdc5'     Parameter: '@wssp18' Type: Bit Size: 0 Direction: Input Value: 'False'     Parameter: '@wssp19' Type: Int Size: 0 Direction: Output Value: ''

Unknown SPRequest error occurred. More information: 0x80131904

System.Runtime.InteropServices.COMException: Exception from HRESULT: 0x80131904  
 at Microsoft.SharePoint.Library.SPRequestInternalClass.DeleteItem(String bstrUrl, String bstrListName, Int32 lID, UInt32 dwDeleteOp, Guid& pgDeleteTransactionId)    
 at Microsoft.SharePoint.Library.SPRequest.DeleteItem(String bstrUrl, String bstrListName, Int32 lID, UInt32 dwDeleteOp, Guid& pgDeleteTransactionId)

I`m out of ideas at the moment. (We will apply update patches and restart the server. and see what will happen :)