Sewell Lexus might be a good place to start. I found this web page from them on the 2007 Gen 4 update but its marked "discontinued" - maybe there is a later one:
http://www.sewellpartsonline.com/parts_det...90137&all=YI've bought quite a bit of stuff from Sewell -- good service. The current discount code from the ClubLexus form is “CL911M” although I've generally been given a discount without using a code. You might want to give them a call to make sure you get the correct update version: 888-909-6633
Don't know if an update would help you locate businesses -- the databases in navigation systems from car manufacturers are often behind the ones in portable navs like the ones from Garmin.
EDIT!: I see on the Sewell website that your 04 GX has Nav generation 2/3 instead of the version 4 in the 04 LX -- Sorry!