is a new shell created for each task in a playbook?

The environment I work in has sudo locked down so you cannot execute /bin/sh using sudo, which is a huge issue because that is exactly what ansible tries to do.

From looking at the output of playbook execution with the -vvvv flag, it seems to me that each task is run in a new ssh session and new shell. Is that correct?

yes, each task runs by issuing a new ssh connection and passing a new shell command.

ansible does not currently work with sudo restricted to specific commands:
http://docs.ansible.com/ansible/become.html#sudo-and-su-still-work (check notes)