Mendoza in Hollywood came out in Hardcover in Jan. 2000, and has just recently come out in Paperback from Tor.

In Mendoza in Hollywood, we find the immortal agent of the Company, Mendoza, roaming the hills of what will be Hollywood looking for rare, mutated, soon to be extinct plants, and living in a stagecoach stop that's run by company operatives, including a whore with a heart of well, it ain't California gold. The Company, as you may know, is a corporation that has control of time travel, though only into the past, and which specializes in turning orphans into immortal cyborg agents who preserve the rare, interesting, or useful for the future.

(Source: Tor Books)