If multiple people are paying you at the same time it is easy to mix up the payments. Most companies use an invoice number to avoid that problem. So I think we need something like a variable length comment field, maybe starting with one byte for size. When there is no comment, the zero byte will add only 4 gas. Using a comments field will be cheaper than registering a new account for every invoice, besides that, it will save memory in the state tree when there are no throw-way accounts.
For the end user, the registration seems like the most expensive part. Being able to do it via the relayer is an obvious way to save on a main chain transaction. So for example, whenever the relayer receives a transfer to a previously unknown address, he puts an unused address index in the to field and puts the 20 byte address in the comments field. So for 21*68=1428 gas extra you can register a new account.