I could've sworn I saw a non-CE version of the VHS in a thrift store but I can't find such a thing anywhere online so apparently this was the only release in NA...?
I'm quite sure there was a VHS release before the Collector's Edition, but it was for rental only. I remember because when The Matrix was first released to home video you could only purchase the DVD initially, and there was a controversy as to why it was only available on VHS to rent, with some believing it had something to do with the Columbine shootings.
I remember it being a big deal when it finally came out on VHS to purchase at major retail many months later because we did not yet have a DVD player and it was my dad's favorite movie at the time. I was with my mom when she bought him the Widescreen VHS at Suncoast for Christmas. This was when the Collector's Edition first appeared.
This appears to be the rental edition, without the featurettes at the end of the tape and no Collector's Edition banner at the bottom of the cover: http://www.ebay.com/itm/The-Matrix-VHS-1999-/320885329329?pt=VHS&hash=item4ab6418db1