It was fairly easy to communicate between frames with JavaScript, so before this was widely adopted, I remember the way we used to “fetch” new data was with an iframe that always had a meta refresh tag in it, and the server response would include JavaScript that would call into functions from the main window passing along any data that was needed.
I might be wrong, but I think even early versions of Gmail did something similar.
People were definitely experimenting with it before that. Developers were mostly using it to load direct server-side snippets of HTML, dynamically. It took the evolution of SOAP and (especially) JSON/RESTful APIs for it to start seeing mass adoption as the combined technology of "AJAX".
Prototype.js and jQuery had a big hand in the latter.
what made Gmail memorable was cross browser ajax. Prior to, you had things like OWA but it only worked right in IE.
The big inbetween OWA and Gmail, was Oddpost, which was also IE only, and was purchased by Yahoo three months after gmails April Fool announcement, to become Yahoo Mail. In a roundabout way, you can argue gmail was a copy of what was eventually Yahoo Mail.
