How can I select users that are not members of any user groups? I'm struggling to find a way to use craft.users to select all users that are not members of any groups. Looking at the User Element Type both the groupId and group parameters are used to perform additional queries which will return nothing unless a valid group Id or handle is provided... I think.

Is it possible to find users not in groups or will I have to do this post retrieving all users... I need to paginate the results so this is not ideal.
You could get the IDs of all users belonging to a group, and use these IDs prefixed with not as the id parameter in a second craft.users ElementCriteriaModel:

{% set userIds = craft.users.group('group1, group2, group3').ids() %}
{% set users = craft.users.id('and, not ' ~ userIds|join(', not ')) %}