表示されるメッセージが分からないのですが、削除したファイルはPCに保存したものを右クリックして削除しているのでしょうか。
削除したファイルの元の保存場所、削除の具体的な方法、表示されるメッセージなど詳しい状況を投稿してみてください。
ゴミ箱が壊れているということであれば、次の方法を試してみてください。
下のサイトにある「1. 隠しファイルを表示する方法」と「2. システムファイルを表示する方法」で隠されたファイルを表示させる。
下のサイトを参考にPCのCドライブを開く。
下図(Windows 7 の図ですが8.1でも同じです)赤枠の[$RECYCLE.BIN]があれば、右クリックして「名前の変更」で、[$RECYCLE.BIN**.OLD**]などに変更する(下図緑枠)。
変更後にPCを再起動すれば新しい[$RECYCLE.BIN]が作成されます(下図の状態になる)。
これで改善されない場合は、Cドライブ以外のDドライブなどがあれば同じ操作を行う。
改善できたら、リネームした[$RECYCLE.BIN**.OLD**]を削除して、隠されたファイルの表示方法を元に戻す。