As you have the Messiah 2 chip, the latter version of Action Replay is the better for you in your situation.
You mentioned the memory card manager etc. There are also the many extra codes for more recent games. My AR2 is something like v2.23
Look for the exact version printed on the disc in the inside ring (you have to look carefully), older versions are needed for swap chips like Neo2.2 for DVD-R etc.
I wouldn't say you were cheated by the shop, they were just selling you what they had, but then it depends on where you got it from. HMV etc stock the latest versions.