Songs aren't playing in the order listed.

My playlist displays songs in the correct order but plays them in a different order every time even though shuffle is OFF.

It might make sense to me if it played them in the same (wrong) order every time, but the order is different each time, even when using the next/previous song button.

I have the iPhone 4s. iOS 5.0.1

I created the playlist on my Iphone and added the songs individually.

The "Group By Album Artist" under Settings - Music is OFF

I noticed this before on my last iPhone 3G when listening to purchased audiobooks. Not cool when it plays the chapters in the wrong order...

No matter how I view the songs on my phone (by playlists, artist, songs or albums) the songs don't play in the order the are listed.

Is there a hidden shuffle-type function somewhere?

When you are viewing the screen (in portrait) while the song is playing, if you tap the screen once, just below the song info, you should see a new bar pop down that shows the time of the song and on the left, 2 arrows that go in a circle, and on the right 2 arrows that cross each other. My guess is the 2 arrows that cross are blue or selected. Give that a try. I had the same issue before if I am reading your post correct.