The answer to your title question -- "Should I upgrade?" -- is, I believe, yes; assuming you have the money to do so. Your home theater should be a source of enjoyment and relaxation for you. If the shortcomings of your receiver are causing annoyance, IMO it is time to look into another receiver. No reason to wait; they will always be coming out with new techologies so waiting won't do much good.
As to whether or not you should get separates, that is something only you can answer. If money is no object, why not? However, if your only goal is to eliminate the source of your annoyance, a good receiver will do fine. If you do opt for separates, I don't think there's any reason to spend a fortune. IMO you tend to reach a point of diminishing returns. Sure you can pay $20,000 for an amp but will it sound five times as good as a $5,000 amp? IMO no. In fact, I submit that there is little, if any, audible difference in SQ between them.
All of the receiver brands you mentioned (with the exception of B&W, which is a speaker manufacturer; maybe you meant B&K) include some very nice units. I don't hold the opinion that there vast differences in the sound of similarly priced receivers. Among Denon, Harman Kardon, Integra, Marantz, NAD, Pioneer/Pio Elite and Yamaha, pick one that has the power, features, look and ergonomics you want/need. If you want to step up a tad in build quality, you might look at Arcam, B&K and Rotel.
To THX or not to THX. It's merely an indication that the model has been reviewed by George Lucas' engineers and is certified to provide accurate movie playback. Some manufacturer's submit their gear for certification (and pay for it, theoretically thereby adding to the price of it) and some do not. It does not mean that if a product does not bear the THX certification that the product could not meet the requirements for certification if submitted.
At the end of your post, you comment that, "Im just always looking to improve. . ." Well, upgrading your speakers will give you most noticable improvement in SQ. Just a thought.