All messages search doesn't seem to include "all messages"

you would need to correct the timestamp of the messages with extractors or the processing pipelines.

I guess the syslog messages did not include timezone information but as written it is possible to correct that. This community board include some posts that had that explained.

One example to correct the time with a processing pipeline rule could be:

rule "cisco (3.3) correct timestamp NEXUS"
// we want to create ISO8601 Timestamps
// make '2015 Feb 15 13:33:22.111' ISO8601
when
    has_field("cisco_message") AND
    has_field("log_date") AND
    grok(pattern: "%{YEAR} %{MONTH} %{MONTHDAY} %{TIME}", value:to_string($message.log_date)).matches == true
then
    let time = parse_date(value:to_string($message.log_date), pattern:"yyyy MMM dd HH:mm:ss.SSS", timezone:"UTC");
    set_field("timestamp",time);

end

The above is taken from this blog post: https://jalogisch.de/2018/working-with-cisco-asa-nexus-on-graylog/