Thx for the reply, see my post EDIT2
It 's a shame such a big file hoster does not resolve this problem.
I think I'll contact them and tell them the same I did here:
If this problem persists I might change to another hoster...

EDIT:
Sent a message under BUG REPORT:

Hello,

it appears that the linkchecker from FS is encountering problems.
Links appear to be online but when you actually want to download them the files are missing/deleted.

Please fix this problem.
I think it's a shame such a big file hosting company encounters these errors.
If the problem persists for the next months I'm not sure if I'll renew my premium account...

There have been numurous reports about this and seems to be going on for the past 6 months!

I sincerely hope this gets fixed soon.

Thank you.