Is form data cached?
As far as I know, Drupal doesn't cache submitted form data. However, generated HTML Code is cached in many places.

I've come upon this problem when rendering a form in a block produced by a custom module. If block caching is active and the form is sometimes rendered with some fields pre-filled (The user's name, the previously used search term), that version of the form might be cached and displayed to other users.
This particular case is easily fixed by setting $block['my_block']['cache'] = DRUPAL_NO_CACHE; in your module's implementation of hook_block_info.