What you are seeing is actually a good thing -- this means that the clients people are using are following the HTTP recommendation::

From the HTTP/1.1 specs, section 15:

5.1.3 Encoding Sensitive Information in URI's

Because the source of a link might be private information or might reveal an otherwise private information source, it is strongly recommended that the user be able to select whether or not the Referer field is sent. For example, a browser client could have a toggle switch for browsing openly/anonymously, which would respectively enable/disable the sending of Referer and From information.

Clients SHOULD NOT include a Referer header field in a (non-secure) HTTP request if the referring page was transferred with a secure protocol.

Depending on how sensitive the fact is that someone was redirected to the insecure site from the secure site, you could encrypt a timestamp with a two-way key, that both servers know, so the receiving server can decrypt the timestamp, and check if it's current.