Removing leftovers?

If I create a mesh, and then choose to delete it (A, X->All), the object still remains. Now, I noticed that I can still select the leftovers from the Outliner, but I can’t seem to delete it. Is there a proper way to do this?

You need to delete the object in object mode to delete it properly.

Now I feel stupid. I thought I tried that a number of times. Oh well. Thanks.