<p>I need to build something that starts serving a H.264 encoded video to a flash player halfway through the file (to support skipping to a point in the video that has not been buffered yet). </p>

<p>Currently, the videos are in the FLV container format, but transcoding is an option. I managed to re-write the file header and metadata information for a given byte offset. This works for older videos, but not for H.264 encoded files. I suspect this is because the video tags inside the file also have to be altered, which is not feasible (it would take too much processing power).</p>

<p>What is the "proper" way to do it?</p>

@yoavf - I think the OP is interested in server-side aspects of streaming on-demand h.264 inside of FLV files.  Reuse of existing players would be nice for him, I think.  Or maybe that is my own needs coming out?  <:S
From yoavf's second link, there is another link to Tinic Uro's
What just happened to video on the web?
.  A relevant quote:
Will it be possible to place H.264 streams into the traditional FLV file structure? It will, but we strongly encourage everyone to embrace the new standard file format. There are functional limits with the FLV structure when streaming H.264 which we could not overcome without a redesign of the file format. This is one reason we are moving away from the traditional FLV file structure. Specifically dealing with sequence headers and enders is tricky with FLV streams.
So, it seems one can either tinker with ffmpeg encoding (if that is how you are getting your FLVs, like I am) or one can get into the new format.  Hmmmm....