Count me in and weigh me

I know that some of you guyz have seen this one before, but if you havn't its pretty hard..

Here is the situation:
You are working for Fort Knox, and are responsible for storing the gold in large safes.
One day your boss walks up and has some bad news:
"Ok, someone screwed up. They delivered a package here that contains fake gold. The only way
to recognize the package is by its weight, so you will have to weigh every package and see
if it is lighter than the others. I already spoke with the folks at registry and narrowed it
down to 512000 packets, which is still a lot I guess. You have time until tomorrow to find the
quickest way to get the job done. I can get 4 scales from town, but every scale will only
hold 1000 packages max. Also you won't be able to get the weight from these scales, but you will
easily see the difference if the fake package is on one of these scales, of course only if all
the scales have the exact same number of packages on them. I want you to find the way that needs
the fewest scale attempts for the worst case scenario.
For every scaling you can put a stack of packages (not more than 1000 for every stack) on each of
the four scales, and see the difference between those four stacks of packages.
When you have the procedure please find the number of scale attempts needed for the best case and
the worst case and report with the numbers to me tomorrow. I hope it is better than mine, because
if not I may just fire you."

Hope its figured out!