Using transients to store form notifications

I would use user ID then user IP if not logged in, you can store the result like the following:

/*
your form validation/submission logiccode goes here
*/

$max_execution_tim = @ini_get('max_execution_time'); 
$submission_result = array('message' => 'Worked!', 'status' => 'success');

// You can use this function:
// https://stackoverflow.com/a/6718472/1321398
$user_ip = GetIP();
$transient_name = is_user_logged_in() ? "form_submission_user-" .         
get_current_user_id() : "form_submission_anonimous-" . $user_ip ;
// save it for a minute
set_transient( $transient_name, $submission_result, 1 * MINUTE_IN_SECONDS );

Then you can check before outputting the form:

$user_ip = GetIP();
$transient_name = is_user_logged_in() ? "form_submission_user-" . 
get_current_user_id() : "form_submission_anonimous-" . $user_ip ;
if( $submission_result = get_transient( $transient_name ) ){
    //show your message
    echo $submission_result['message'];
    // delete it to avoid duplicated messages
    delete_transient( $transient_name );
}