How well do you know her?
Have you been paying attention to conversations you have had in the past, was there something she mentioned that she always liked or loved?
As an example, an ex of mine, in passing was telling me about a book she used to read as a child that has had many reprints, and that the one she used to get from the library where she grew up sold it after a few years of her moving. She's never seen the same edition of the book since.
7 months later, for her birthday, (after 5 months of a lot of searching, found it in some American secondhand book store), I managed to get a print of the edition she meant, as I made a mental note of how she described the cover.
Something like that should be proof enough, lol