I Personally Believe Peter Denied Christ Exactly Six Times
I did a study of this exact problem in my seminary studies for my M.Div., and just looking at the textual details and collating the accounts came to the conclusion that the answer is best resolved as seeing it as two sets of denials of three each, with each group of the three occurring prior to a cock crowing. I offer the summary of my observations from that study below as to how this works.
The prophecy as related in Mark 14:30 is the only one to note two cock crows, and the construction is such that it can be read as "that you today, in this night, before twice the cock crows, thrice you will deny me." Now this could be understood as three denials followed by two cock crows, or it can be three denials, followed by a crow, and three other denials, followed by a crow. But to fit the other recordings of the specifics of the prophecy, that before the cock crows three denials will happen, it logically can only be the latter. Additionally, even in the fulfillment of Mark, the crows are separated in time (Mk 14:68, 72).
So here is a summary of what I came up with as a synthesis of the accounts:
Prophecy (Mt 26:34, Mk 14:30, Lk 22:34, Jn 13:38)
Comparison indicates no cock crowing can occur until at least three denials, but that there are two cock crows that will occur (as I just noted above).
1st Denial (Mt 26:51a-b; Mk 14:54a-b; Lk n/a; Jn 18:16-17)
A young woman at the door upon entering the palace. Only John records the denial, Matthew and Mark only note the entry into the palace, and Luke is silent about this.
2nd Denial (Mt n/a; Mk n/a; Lk 22:55a; Jn 18:18, 25)
Luke only notes the fire, and again it is John's gospel that is the only witness to this denial, which is to "servants and officers" standing around warming themselves at a fire, as Peter stood warming himself. It is "they" who confront him (v.25).
3rd Denial (Mt 26:58c-d; 69-71a; Mk 14:54c-d, 66-68; Lk 22:55b-57; Jn n/a)
John is not a witness of this encounter. Peter is now sitting by the fire (the night is growing longer), and a young woman comes and states she saw Peter with Jesus, which he denies, but now he is getting edgy, because the group thought he was one, and then this young woman came among them and stated the same thing. So Peter leaves the fire and goes "out into the porch" at which time there the...
1st Cock Crow Occurred (Mk 14:68 only)
It states it was as Peter went out into the porch that the crow occurs.
4th Denial (Mt 26:71b-72; Mk 14:69-70a; Lk n/a; Jn n/a)
Luke and John are silent here, but another young woman comes, which we know was after his going out into the porch from both accounts, and after the first cock crow from Mark's account, and she confronts Peter and he denies.
5th Denial (Lk 22:58 only)
This is a lone mention by Luke, that occurs after his sitting by the fire (denial #3), for Luke recorded that denial, but this denial is, based off Peter's reply, to a "man" (which means it is not a reference to denial #4, which was a young woman).
6th Denial (Mt 26:73-74a; Mk 70b-71; Lk 22:59-60a; Jn 18:26-27a)
This is the only denial noted by all four accounts. That it is the last one puts emphasis on it. The three synoptic gospels (Mt, Mk, Lk) mention the speech/ethnic aspect that alerts them to Peter. There is a group that accuses him, but John seems to mention a specific one accusing Peter, who was in relation to the one whose ear Peter cut off in the garden (and was himself apparently in the garden at the time, which may be why he was confident Peter was with Jesus, as Luke records of this witness, and why the vehement reaction recorded of Peter's denial in the other three accounts). There is nothing contradictory about John focusing on one, though other accounts note a group.1 That one was obviously a key witness against Peter! Now it could be possible that John's account is of the 5th denial instead, but there is one piece of evidence that lead me to place John's final account in line with these others--he, like Matthew and Luke, both note that "immediately" after that denial the...
2nd Cock Crow Occurred (Mt 26:74b-75; Mk 14:72; Lk 22:60b-62; Jn 18:27b)
Again, we only know it is the 2nd crowing from Mark, but it is the final denial in all four accounts. The other three accounts only record this crowing.
Why so Cryptic - Where at First Reading it Seems to be Three?
My study was simply on the correlation of facts noted to resolve the accounts as all being truthful and inerrant. There had to be a rhetorical (and perhaps other) reason God had each writer record differing sets of only three denials each. I have not yet studied out that, and am not sure a full answer could be had (at that point we are getting into "why" God did it that way, not "that" He did it that way).
However, my first thought was for it to be a potential stumbling block to unbelievers. An unbelieving, cursory reader will think there is "error" in the Bible because a quick reading would make it impossible to see the connections of the accounts. History has proven that unbelievers try to use these discrepancies to disprove the truthfulness of Scripture. One should always approach God's word as true (in faith, as HIS word of TRUTH [part of my hermeneutic]) and then try to resolve the tensions that seeing it as truth may make. I believe there is always a logical, truthful resolution to any tension in Scripture--but whether we always have all the knowledge we need to resolve it may not be so.
Would God intentionally set up such a potential stumbling block? Certainly. He tests faith in many ways, and this is no different than testing Adam to not eat of that one tree in the garden. That was a potential stumbling block to not having faith if there ever was one. The fact that God can set up such a scenario as Peter's denial and record it in four differing ways, and yet make each account still communicate truth is fascinating (any one account read alone speaks truth, but differing truths; and all accounts collated together speaks truth).
Of course, my view messes up (slightly) the nice parallel of Peter's three affirmations of love for Christ in John 21 (which many preachers I have heard will parallel to the three denials). However, rhetorically speaking, there is still the possibility of connection, because John only records three denials. So in the context of John's gospel, the parallel still holds up well.
Six Times Not Original to Me
The study I did was my own, but it was prompted by a quick statement alluding to the possibility of six denials by a professor of mine in school. He, in turn, got the thought from an end or foot note in a book. Unfortunately, at the moment I do not have the reference to that book to give (but I thought I should note it ultimately sparked the chain reaction of my investigation of the passages).2
UPDATE (6-11-2014)
I have since found a lengthy discussion of six or more denials in Appendix H (starting on p.229 [235 of the pdf]) of Wilbur Pickering's The Identity of the New Testament Text IV (2014) that also discusses some of the textual variant issues between the manuscripts.
NOTES
1 The reason to not align the 2nd and 3rd denials is not primarily because the 2nd mentions a group, and the 3rd a young woman, as a group is still present during the 3rd denial. Rather, the key is Peter's posture. He is standing at the 2nd, sitting at the 3rd. In the 6th denial, there is nothing to contradict placing John's account with the other four--having the individual be a focus upon one within the group, who seem to be interrogating him.
2 A quick internet search found some others noting or advocating (not exactly in line with my articulation) a six denial view. The first reference states, "The six-denials approach was popularized by Harold Lindsell in his 1976 book, The Battle for the Bible." This could be the book that my instructor was referencing.