The solution I thougth to this problem, is to dedicate as much hashing power as possible to new accounts, so they will be able to become completed quickly.