So lets say, I run a fictional ebay account selling goods to people and I want to accept BTC.  Everytime I make a sale and someone wants to pay me in BTC, I go into my Bitcoin client go to address book and click on receiving, and then select my ebay receiving BTC address.  I copy it to clipboard and email it off to the customer to pay me, and wait on their payment to arrive before I ship.

This is all fine and good until I have more than 1 customers who haven't paid.  I somehow need to verify which customers have paid and which ones have not.  But I cannot tell that by looking at the addresses of coins I receive via Bitcoin.  Okay, maybe the items cost different amounts and I can distinguish the orders by looking at the price, but say all the items cost $5.99 so price alone can't determine the customer.

Is there a solution to this problem?  Do I have to create a new address for every new order?