Had some recent cleat compatibility issues myself, I've always used VP104 SPD's with VP cleats on all my bikes. Recently purchased a pair of Shimano M520's for my road bike, the Shimano cleats work brilliantly with the VP pedals. The Shimano cleats give you a positive loud click on both types of pedals which you don't get with the VP cleats, unclipping is much more positive and consistent. I since have bought another pair of Shimano single release cleats to use with the VP pedals on my MTB's.
VP - Wellgo - Tioga pedals all use the same cleats as far as I know.