This in an old question but I think it is a good one.
As you mention I,P and B frames, in 2012 you are likely referring to H.264 over RTP.
According to [rfc6184]1 , the marker bit is set on the last packet of a frame , so indeed the marker bit can be used as an indicator of the end of 1 frame and the next packet in sequence will be the start of the next frame.
According to this rfc, all packets of a frame also have the same RTPTIME so changes in RTPTIME is another indicator of the ending of the previous frame and start of a new frame.
Things get more tricky when you lose packets. For example, let's say you lose packets 5 and 6 and that these were the last packet of frame 1 and the first packet of frame 2. You know to discard frame 1 because you never got a packet with a marker bit for that frame, but how can you know if frame 2 is whole or not. Maybe the 2 lost packets were both part of frame 1 or maybe the second packet was part of frame 2?
rfc6184 defines the start bit that is present in the first packet of a fragmented NAL unit. If the NAL unit is not fragmented then by definition, we got the whole NAL unit if we got the packet. This means that we can know if we got a full NAL unit. Unfortunately, this does not guarantee we have the full frame since a frame could contain multiple NAL units (e.g. multiple slices) and we may have lost the first one. I don't have a solution for this problem but maybe somone will provide one sometime in the next 10 years.