Oh. My. Lord. This thread has basically just been a blog. lol
But, the good news is that my host figured out the cause… I forget the name of the module, but PHP was encrypting the cookies. As soon as he turned that off – everything works peachy.
What little hair I had left is gone now though.