MD5 hashing does not match in C# and PHP

Your problem is here:

Guid r = new Guid(encodedBytes);
string hashString = r.ToString("N");

I'm not sure why you're loading your encoded bytes into a Guid, but that is not the correct way to convert bytes back to a string. Use BitConverter instead:

string testString = "123";
byte[] asciiBytes = ASCIIEncoding.ASCII.GetBytes(testString);
byte[] hashedBytes = MD5CryptoServiceProvider.Create().ComputeHash(asciiBytes);
string hashedString = BitConverter.ToString(hashedBytes).Replace("-", "").ToLower();
// hashString == 202cb962ac59075b964b07152d234b70