Old DOS tricks:

Copy another file with the same name overtop (Do you want to overwrite, yes)... then try deleting.

Try actually formatting the memory card.

There was an app that would defragment the memory card in the apps section of www.maemo.org. Mayhaps it'll shuffle stuff around.

Sounds like you've got the memory equivalent of a bad sector.