R2-D2 was Padme's droid, not Anakin's, already in 'Phantom Menace' Although he spent a great deal of time with Anakin, his loyalties lied with Padme. When Padme died (at the end of 'Revenge of the Sith'), he was 'inherited' by Leia in custody of Bail Organa.

When Anakin was subverted by the Dark side, he did not care about R2 (or C-3PO). He did not try to convert the droids (at least we do not see it in the movie).

So the Rebels had no reason to doubt R2's loyalty.

The simple answer is they don't know. Most of the Galaxy didn't know that Darth Vader was Anakin Skywalker until decades after Return of the Jedi. The whole book about in the new continuity. It is revealed that most of the Imperials didn't even know.

    People in Star Wars universe tend to take droids for granted, and treat them like equipment. RD-D2, C-3PO or Chopper from Rebels often succeed in some missions because enemies (Imperials or otherwise) ignore them and let them move around trough secure areas without much hassle. On the other hand, sentient living beings would be much more scrutinized.

     This behavior is not entirely unrealistic. Even in real life, how many people would suspect or even think about possibility that their smartphone or computer is spying on them ? Yet, we know for a fact from recent NSA scandal that such thing is not only possible but very real and in fact used for surveillance and gathering of data.

The Rebellion didn't appear overnight. Immediately after Vader's crippling on Mustafar, R2-D2 passed into the service of Senator Organa, and it took many years to build up the Rebel Alliance. There is plenty of time there for R2's loyalties to be tested and confirmed.

Spy droids do exist, yes, but they're not exactly...subtle.

• R3-S6 was in an excellent position to spy on the Republic, but instead he gave himself away with a series of clumsy sabotage attempts
• EXD-9 was an Imperial infiltration unit deployed during the Galactic Civil War to locate rebel bases. As soon as it heard confirmation that it had found such a base, it immediately converted into battle mode and started trying to kill everyone.
• C1-10P worked for the rebellion, and was frequently employed as an infiltration unit. He demonstrated a very single-minded attitude, and would go straight for his target as soon as he was in place.

What we've never seen is any kind of droid used as a mole, a long-term plant biding its time until the perfect moment.

In the Rebels episode Droids in Distress, R2-D2 and C-3P0 were lent to an Imperial official, Minister Maketh Tua, to help facilitate the purchase of some banned weapons; R2 was also given the secret mission to keep the weapons out of imperial hands. The mission was completed.

Anakin was not the only person R2-D2 had a bond with. He also worked very closely with Ahsoka Tano, who would call him "Artooey". Ahsoka was a member of the Rebel Alliance, and would almost certainly have been able to both ensure R2's loyalty and, if necessary, check his programming.

In short, then, we don't see droids being used as long-term plants, R2's loyalty was never that compromised to begin with, and he had been tested in at least one (and probably many more) less critical missions during the initial formation of the Alliance.

During the time that R2 worked with Anakin, Anakin was a good guy. So he would have had no reason to try and control R2 during that time. They both served wholeheartedly and were committed to the ideals of the Republic. R2 wasn't just a droid serving a master. He displayed self-awareness and self-motivation many times. (Which was one reason Anakin liked him so much - he had a unique personality with a bit of a rebellious streak, like Anakin himself.) So in order to turn R2 into a weapon of Vader, someone would more than likely have had to wipe and reprogram him.

Anakin's fall to the dark side was rapid and sudden. Even as he questioned the council and the Jedi, he still believed in the Republic, and even the council. He informed Mace Windu about his suspicions about Palpatine. He wanted Palpatine arrested. It was only when Windu tried to kill Palpatine that he felt he was given no choice but to stop Windu in order to preserve the knowledge he needed to save Padme. That was when he finally embraced the dark side, and from that point to the point when he arrived on Mustafar, there wasn't enough time for him to do anything to R2. Certainly not anything that wouldn't be immediately noticed by someone who knew R2.

This brings up another interesting question: Why was C3PO's mind wiped, while R2's wasn't? One important distinction was that, while R2 served alongside Anakin often, C3PO was actually built by Anakin. Perhaps they were afraid that Anakin would have some mechanism to control C3PO?

When Anakin found out Palpatine was Sith, he reported it directly to his superiors. When we see Mace Windu fight Palpatine, Skywalker shows up mid-fight. Mace is happy for help to arrive. It is only after that when he became Vader.

In other words, the Jedi are pretty fairly certain that Anakin wasn't a traitor the whole time.

R2 wasn't with Vader at any point after his conversion. Therefore, there was no opportunity for R2 to be programmed with any spy routines.

Another factor to consider is that even if Skywalker had been a double agent for a long time, there wasn't a rebellion. No way to program R2 to spy on something that doesn't exist.

not the droids you are looking for (but...)

Out-of-universe theory here.

Basically: R2D2 and C3PO got in the prequels because they were supposed to raise sales for the prequel movies.

Ask: which characters could you use if you were to continue building your "star wars" brand, doubling the screen time?

The prequels mark a shift to unprecedented heights of merchandizing aggressiveness, or so I claim. Before them, I certainly don't remember getting SW character photos on every other mug I came across.

Before the prequels were made, arguably the most established thing about the past was that Kenobi and Mr. Skywalker, sr. fought together, were teacher-and-apprentice, and that Yoda knew about it all.

You can't show Vader, Kenobi will look different and there is Yoda. (Who did become heavy on mugs.)

But you also got a lot more of these, shall I say 'prop' characters - characters who look the same in every episode, because, well, they're props, costumes, effects. Chewbacca, Jabba, R2D2, C3PO...

In the original trilogy I always liked R2D2 and C3PO - who didn't? When I was watching The Phantom Menace in the theatre and C3PO showed up, personally I felt that something went horribly wrong with these sequels. It's such a stretch that Anakin would have built C3PO. Seriously? In the entire galaxy, the galaxy which any audience could've expected to see more its exotica of, the very same two robots just happen to show up in all the important moments and places, all along?

The reason Kenobi trusted them in the New Hope is because they are a continuity bug introduced by the prequels, ie. their inclusion is for an out-of-universe reason, that was carried out despite all the in-universe inconsistency it caused (together with so much else), and with Alec Guinness dead they couldn't yet butcher in new replacement original trilogy scenes to make up for it.

A nice (even if a bit difficult to hold) theory is that R2 is considered a Key member or the rebels (probably following its long story of good attitude and cleverness). See http://fantheories.wikia.com/wiki/Star_Wars#Chewbacca_and_R2D2:_Secret_Rebel_Agents

(in a nutshell: this link shows many parts of episode IV hinting that R2 knew a lot about luke, obi-wan, etc, and had to in order to succeed his missions)

This explains at least the "not wiping its memory" part, and I have to say that R2 did a great job staying undercover while being undoutably very efficient in carrying its missions...

IG-88 was programmed to kill, but apparently he was not told to follow orders, because he killed his creators, and went into business for himself. (Itself?)

K2SO was reprogrammed, and obeyed rebel orders, because he was programmed to do so. Killing didn't seem to be a problem, so long as they were considered "hostiles".

R2D2 was sold to Luke, but continued to be loyal to his mission to find Ben.(Another internal secret map? REALLY ARTOO?) Obviously his programming knew the sale was not legal, and he still had a mission to fulfill.

C3P0 Told Luke in "A new Hope" that he wanted to take a nap (Shut down to recharge?) after his bath, and asked Luke's permission. He made sure he was not needed, but had enough control over himself to power cycle. He also apparently could turn himself back on, because he said he TRIED to stop Artoo from leaving, and then hid himself to avoid being punished.

This concept is shown again in "The Force Awakens" when Artoo had been in "low power mode" for a while but was able to turn himself back on when the proper time arose for him to share his section of the map.

"I didn't hit it THAT HARD, it must have had some sort of self-destruct" Was what Han Solo said after shooting the Imperial Probe-Droid on Hoth, and it's explosion. "There isn't much left". So the droid knew it might be captured and hacked, and either CHOSE to end itself, or it was programmed to do so.

If a droid can turn itself on and off, and can even kill itself, chances are, it would not be hard to erase it's own memory. Artoo is pretty quick to zap ANYONE with a tazer. Rerouting some amperage inside wouldn't be that hard for him to do, astromech droids repair ships IN FLIGHT and DURING COMBAT, as seen in "The Phantom Menace". So quick thinking and improvising a memory wipe shouldn't take long.

When Artoo was hacking the DeathStar, it DID take a few moments, someone hacking him should also take a tiny bit of time, but Artoo is quick.

K2SO was also Quick to hack another droid, but he was VERY familiar with that model, and how to hack it. Even though he used the quick Robo-Cop style stab and hack, I think Artoo would have been able to nuke his files before they were discovered.

Keeping mission files loaded in short-term ram would be another option. Anything on e-prom or hard drive (yes they use hard drives, watch "Rouge One") Could be pulled up if he were disabled, by lets say.. an Jawa droid stunner? But anything in ram would be lost when power cycled, or just from the sheer power coursing through his circuits from the discharge.

R2D2 had proven his loyalty many times. But, he could have also been blindly following orders as he was programmed to do.