Even if OmniDiskSweeper (which I've been highly recommending for years) does the job and finds lots of stuff you can erase and free up HD space, this still doesn't explain why the Finder doesn't manage to reclaim HD space. If you delete 500 MB of files and empty the trash, the Finder should show 500 MB more free HD space.
Of course once the HD is *SO* full, the system is constantly running amok, and this has to be kept in mind. Since the system tries to write virtual memory (and can't, because the HD is basically full), you erasing 500 MB will simply lead to the system taking over that space with VM and you'll see that your HD continues to be more or less full. You'll have to erase GIGABYTES before noticing a real effect.
As Giaguara said: Keep 15% (or 10% or 20%) of HD space free at all times. The more the better. Of my MacBook Air's 80 GB of HD space, I have 25 GB free at the moment, and I don't intend to fill it up more, rather I'm going to erase a couple of gigabytes. Mind me: I have tons of GB I *could* put on the MacBook Air, but in order for it to remain a quick little machine, the harddrive needs its space freed up.
If you let the HD get filled up, you're simply _asking_ for problems.