Cannot delete/move files with special characters in file name

A simple way would be to remove these files by their inode. :)

Use ls -li in the directory with the uncommon characters to show the inode number of each file, e.g.,

$ ls -li
total 0
133370 -rw-r--r-- 1 malte malte 0 Dec 30 19:00 ?2?.???љ?!?Gb??σ?[?F?
132584 -rw-r--r-- 1 malte malte 0 Dec 30 18:59 ??3]d???:????????1????G?p?ȋ??????嫳?d????ą-??

Next, use the find utility to delete the corresponding file by its name, using the syntax find <somepath> -inum <inode_number> -exec rm -i {} \;, as in the following example:

$ find . -inum 133370 -exec rm -i {} \;
rm: remove regular empty file ‘./?2?.???љ?!?Gb??σ?[?F?’? y
$ ls -li
total 0
132584 -rw-r--r-- 1 malte malte 0 Dec 30 18:59 ??3]d???:????????1????G?p?ȋ??????嫳?d????ą-??

The -i option to rm is not really necessary, I just added it to keep you from accidentally removing files you didn't mean to remove. :) It causes rm to ask for confirmation for each file that you want to delete.

If you want to remove multiple files by their inodes, you can use the -o (meaning or) syntax for find:

$ find .  \( -inum 133370 -o -inum 132584 \) -exec rm -i {} \;
rm: remove regular empty file ‘./?2?.???љ?!?Gb??σ?[?F?’? y
rm: remove regular empty file ‘./??3]d???:????????1????G?p?ȋ??????嫳?d????ą-??’? y

You can add more inode numbers by extending the expression in parentheses with more -o -inum <inode_number> expressions.

It is important to understand that this is not the kind of "filesystem corruption" that fsck will help with. As far as the filesystem is concerned, file names can be any sequence of bytes, as long as no single byte has the value 0x00 (ASCII NUL, C end-of-string marker) or 0x2F (/, the directory separator). (If a file name does somehow get a 00 or 2F byte embedded within it, fsck should fix that.)

Rather, what you have is file names that application software (Dolphin, ls) think contain characters that are un-displayable in your "locale", so it is replacing them with placeholder characters. You can't type those characters either, so manipulating the files is harder, but you can do it as long as you do it without ever typing or copying and pasting the name. For instance, if you delete or rename the problem files directly from within Dolphin, that should Just Work (I would go so far as to say that if it doesn't work, that's a bug in Dolphin).

If you need to do something about them from the shell (for instance, if they are owned by root and therefore cannot be modified by a GUI program), you can name them indirectly using "glob" patterns, which will be expanded to the correct sequence(s) of bytes and passed along.

Now, of course, you wouldn't want to delete stuff by accident because your glob pattern matched too much, so my recommendation would be to use the Perl rename utility to convert each filename to its hex encoding:

$ rename '$_ = unpack("H*", $_)' *

This doesn't destroy any information - neither the file itself, nor whatever meaning might originally have been encoded in the filename before it got mangled. It can be undone for specific files with e.g.

$ rename '$_ = pack("H*", $_)' 696d706f7274616e742e646f63

Caution: there are two programs named rename, from different origins; the above commands will only work with the one originating with Perl. In Ubuntu, the one you want is the one from the "rename" package, not the one from the "util-linux" package. rename -h will distinguish: this is what you want...

$ rename -h
Usage:
    rename [ -h|-m|-V ] [ -v ] [ -n ] [ -f ] [ -e|-E perlexpr]*|perlexpr
    [ files ]
# ...

... this is not what you want ...

$ rename -h

Usage:
 rename [options] <expression> <replacement> <file>...
# ...

The key thing to look for is "perlexpr". You might have an older version of the Perl rename that doesn't understand all of the options above, but the command I showed should still work.

Edit: Under 14.04 .5 the perl script that's included for rename does not support the -h switch. You can confirm you have the correct one by checking it's man page with man rename in which case the top line will contain: