I finally got around to creating some sample code to demonstrate how to do Rijndael (AES-256) encryption between PHP and .NET servers.
They key probelm I found was that mcrypt pads the key with zeroes, where the default behaviour in .NET is PKCS7 padding. Use this line in your/net project to mimic the PHP behaviour.
symmetricKey.Padding = PaddingMode.Zeros;
You also have to remove the padded nulls from the end of string after you do the decryption:
The complete working C# and PHP projects are here: