I had a similar problem a year or so ago, and was ableto create a unique id this way:
Both feature classes had a core set od attributes such address ranges, prefix direction, street name, street type. I simply concatenated them into one field called it of all things JoinId. It worked very well for me as both feature classes were up to date in edits.
PreDir&SName&SufDir&LeftFrom&LeftTo&RightFrom&RightTo
That should just about do it....