linux - Deleting a huge 500G does not free disk space

I have a remote server here running Ubuntu (Server Edition).

Yesterday I noticed that 100% of my harddisk space was occupied. There was a log file that grew bigger and bigger, so I deleted it via rm file.foo.

Then I ran df -h but the partition where the file was stored was still hat 100% occupied.

So I thought a reboot might help and ran sudo shutdown -r now.

After waiting some minutes, I couldn't connect to the server via SSH so I asked the guys at the data center to manually restart it.

That worked and the server booted.

So I ran df -h again and now 80% of the partition is occupied (at least something).

Next, I wanted to check what requires that much disk space and ran sudo du -h --max-depth 1 / and the result was:

16K /lost+found
942M    /home
52K /tmp
4.0K    /mnt
236K    /dev

du: cannot access `/proc/17189/task/17189/fd/4': No such file or directory
du: cannot access `/proc/17189/task/17189/fdinfo/4': No such file or directory
du: cannot access `/proc/17189/fd/4': No such file or directory
du: cannot access `/proc/17189/fdinfo/4': No such file or directory
0   /proc
4.0K    /media
4.0K    /opt
4.0K    /srv
32K /root
3.0G    /var

393M    /lib
37M /boot
6.9M    /etc
681M    /usr
4.0K    /selinux
8.0M    /bin
9.0M    /sbin
4.0K    /cdrom
0   /sys
5.0G    /

As you can see in the last line, there are only 5 GB occupied (so the file cannot be in trash or "lost+found") - No way it's there anyway since I used rm command.

So, what's wrong?

My personal guess would be that while the server was restarting, it was somehow cleaning up that huge 500GB file that I removed. Forcing the manual restart probably interrupted that so it was only able to clean up 20% of that.

If my guess is true, what could I do to repair this?

If my guess is wrong, what up with my system then?