Techniques are described for providing enhanced access to stored data and related functionality, such as data stored by a system across multiple alternative storage partitions. At least some of the stored data may be specific to particular users who interact with the system, such as for users to perform tasks supplied by other users. The enhanced data access techniques may include storing at least a subset of each user's associated data on a single storage partition, and then efficiently identifying the storage partition corresponding to a user so that requests from that user may be handled by a computing node associated with that corresponding storage partition. Furthermore, additional data access enhancement techniques may relate to initially identifying an appropriate storage partition for a user and/or for migrating existing user data to a new partition identified as being appropriate for a user.