The problem isn't limited to Memo. It applies to all BCH transactions. Make too many of them without waiting for the next block and you'll have the same problem.
2) If this is a service doing many transactions, their wallet implementation should be sophisticated enough to do right coin selection.