If that property was transferred to the state when the highway was
last expanded wouldn't my property description have to be updated? Is
this a title insurance situation?
You aren't far from the mark, but keep in mind that in the U.S. title to real property is not represented by a certificate for a particular geographic area as it is in most of the U.K. and Australia, for example (the modern U.K. land title system was actually invented in Australia). So, unlike those jurisdictions, the full legal description of what you own may not be consolidated into a single, up to date document.
Instead, in the U.S., people file various documents with the real property records (usually maintained on a county level) of the county where the property is located. These records are indexed by grantee and grantor, not by geographic location.
So, in this case, someone would file a plat for the subdivision you live in and that is a matter of public record. Later on the state transportation department would bring an eminent domain proceeding to seize property for public use in exchange for fair compensation, or would negotiate a non-court ordered sale of the land. The decree transferring the property in an eminent domain proceeding and/or the deed transferring the land to the state, would have been recorded in the real property records. But, if there was a discrepancy between how the owner of the property was described in the deed giving that owner title to the property and the name of the owner in the eminent domain matter, this decree or deed or a replat of the land might not get properly indexed.
If the land was taken while you owned it, you should have received notice of the eminent domain lawsuit, although if you ignored it or failed to realize its significance, a default judgment could have been entered against you in that case with no further notice to you.
If you purchased the land after the land was taken in a commercial real estate transaction, a title company should have identified the recorded documents that took that land away from you and that limitation should be listed in the deed by which you took title
Sometimes the deed will simply reference "all easements of record" since the state highway interest will often be a very restrictive easement rather than outright ownership, since this costs the state less to acquire than outright ownership.
If there is not some reference in the title commitment and the deed conveying the land to you, that references the land that the state took for the highway, then you have a title insurance claim against the title insurance company if this limitation was omitted from the title commitment, and you would have a claim for breach of warranty of title to every prior seller conveying by a warranty deed (which is the norm in arms length sales of real estate for fair market value) that omitted the land taken from the highway after the state took that land.
The designation of the land taken, if it is actually an easement, wouldn't change the legal description of the property although the existing of the easement would have to be mentioned, at least in a general sense ("subject to all easements of record") in the deed, and in a specific sense with a copy of instrument creating the easement in the title commitment. The draft title commitment would normally be disclosed pursuant to a real estate contract prior to closing, with an out from the contract available if the title work revealed had an unacceptable problem.
Even if the land was taken outright, the change in the legal description could be subtle, such as "Lot 1, Block 23 of the Amended and Restated Hillshire Subdivision Plat recorded at Book 456, page 128." And might not note that the original legal description was "Lot 1, Block 23 of the Hillshire Subdivision Plat recorded at Book 34, Page 456."
The change could also be stated as a reservation or limitations on the original property description, such as "Lot 1, Block 23 of the Hillshire Subdivision Plat recorded at Book 34, Page 456, subject to the decree of the Hill Valley County District Court recorded at Book 455, Page 100."
Apart from the missing land. The reason this matters now is that they
are improving the highway again and taking another 17' and do not want
to compensate my for the mature trees that I have screening the house
from the highway, because they are already in the right of way or on
their land depending on which survey is used.
The state is required to pay you an appraised fair market value for the land it takes which you can dispute in court (you pretty much always have to surrender the land and the only real issue is the price). If you think that the money offered is too small for the fair market value of the property you should consider hiring a lawyer and your own appraiser to context the valuation.
But, as you note, if the trees in question are "are already in the right of way or on their land depending on which survey is used" then you don't own them and aren't entitled to compensation from the state for taking the trees. Again, this should have been mentioned five years ago in a title commitment and if it wasn't you may have a warranty of title and/or title insurance claim to compensate you for land you thought you were buying but didn't actually own.
