It does not appear that the regular expression is the issue. I believed the issue to be related to the actual /etc/ssh/sshd_config file as there is a difference in the last byte in two test environments I setup, one of which I get this bug on and the other I do not. The one I am getting this bug on does not have the EOF [0a] byte at the end:

I rebuilt nodes in the failing environment and only ran the common-setup playbook which resulted in getting this bug again:
BEFORE RUNNING THE PLAYBOOK:
root@melv7301-infra1:/opt/os-ansible-deployment/rpc_deployment# xxd /etc/ssh/sshd_config
...
00009d0: 0a50 6173 7377 6f72 6441 7574 6865 6e74  .PasswordAuthent
00009e0: 6963 6174 696f 6e20 7965 73              ication yes
root@melv7301-infra1:/opt/os-ansible-deployment/rpc_deployment#
root@melv7301-infra1:/opt/os-ansible-deployment/rpc_deployment# ssh n02
Welcome to Ubuntu 14.04.2 LTS (GNU/Linux 3.13.0-46-generic x86_64)

 * Documentation:  https://help.ubuntu.com/
Last login: Mon Apr 13 23:36:26 2015 from ...
root@melv7301-infra2:~#

RUNNING THE PLAYBOOK
root@melv7301-infra1:/opt/os-ansible-deployment/rpc_deployment# ansible-playbook -vvvv -e @/etc/rpc_deploy/user_variables.yml playbooks/setup/setup-common.yml
...
PLAY RECAP ******************************************************************** 
compute1                   : ok=51   changed=36   unreachable=0    failed=0   
compute2                   : ok=51   changed=36   unreachable=0    failed=0   
infra1                     : ok=51   changed=36   unreachable=0    failed=0   
infra2                     : ok=51   changed=36   unreachable=0    failed=0   
infra3                     : ok=51   changed=36   unreachable=0    failed=0   
logger1                    : ok=51   changed=36   unreachable=0    failed=0   
storage1                   : ok=51   changed=36   unreachable=0    failed=0   

root@melv7301-infra1:/opt/os-ansible-deployment/rpc_deployment# ssh n02
ssh: connect to host n02 port 22: Connection refused
root@melv7301-infra1:/opt/os-ansible-deployment/rpc_deployment#

root@melv7301-infra1:~# xxd /etc/ssh/sshd_config
...
00009e0: 6e20 7965 734d 6178 5365 7373 696f 6e73  n yesMaxSessions
00009f0: 2035 3030 0a                              500.
root@melv7301-infra1:~#

Again, to test, I accessed each server via their console, resolved the SSH login issue, and removed the last byte [EOF] from two of them along with the MaxSessions 500 addition, ran the same playbook again [common-setup.yml] and the two nodes without the EOF byte both replicated this bug while the others did not.

[I used xxd, wc -c, and truncate to ensure I removed the 0a byte from the files on the two mentioned nodes]

So finally, I noticed that the versions of Ansible in my two test environments were different. This bug is related to the version of Ansible being used [1.6.10] in the requirements.txt file and adding ^ to the beginning of the regular expression did not resolve. I have not at this time determined the cause in terms of the way the code handles the file because it is missing the 0a byte at the end however Ansible v1.9.0.1 does not have this problem.

Unless there is a reason to keep 1.6.10 in the requirements.txt file then it may be best to update the version of Ansible being used to the latest stable release or patch v1.6.10. In conclusion, issue is definitely with the lineinfile module.