There may be a quicker/more concise way to do this, but I did it by combining a JavaScriptConverter with a helper type.
The converter (simpler than it looks, inspired from here):
private class RecordPropertyJavaScriptConverter : JavaScriptConverter
{
    private static readonly Type[] _supportedTypes = new[]
    {
        typeof(record_group)
    };
    public override IEnumerable<Type> SupportedTypes
    {
        get { return _supportedTypes; }
    }
    public override object Deserialize(IDictionary<string, object> dictionary, Type type, JavaScriptSerializer serializer)
    {
        if (type == typeof(record_group))
        {
            record_group obj = new record_group();
            var kvp = dictionary.Single();
            obj.Key = kvp.Key;
            obj.Values = serializer.ConvertToType<IEnumerable<object>>(kvp.Value);
            return obj;
        }
        return null;
    }
    public override IDictionary<string, object> Serialize(object obj, JavaScriptSerializer serializer)
    {
        var dataObj = obj as record_group;
        if (dataObj != null)
        {
            return new Dictionary<string, object>
            {
                {dataObj.Key,  dataObj.Values}
            };
        }
        return new Dictionary<string, object>();
    }
}
The helper type:
private class record_group
{
    public string Key;
    public IEnumerable<object> Values;
}
The serialization code:
var groups = recList.GroupBy(r => r.Key)
                    .Select(g => new record_group { Key = g.Key, Values = g.Select(r => r.Value) });
JavaScriptSerializer serializer = new JavaScriptSerializer();
serializer.RegisterConverters(new [] {new RecordPropertyJavaScriptConverter()});
string json = serializer.Serialize(groups);
The output (with some tabs, newlines added by me):
[{"P_Flavor":["Berry","Cedar","Cherry","Coffee"]},
 {"P_Winery":["Lyeth"]},
 {"P_Body":["Elegant","Firm","Firm Tannins","Polished","Supple","Tannins"]},
 {"P_Name":["A Red Blend"]},
 {"P_DateReviewed":["08/31/95"]},
 {"P_WineID":[34699]},
 {"P_Score":[5]}]
Deserialization can then be done (using the same serializer instance from above) as follows:
var deserialized = serializer.Deserialize<IEnumerable<record_group>>(json);
var properties = deserialized.SelectMany(g => g.Values.Select(v => new record_property { Key = g.Key, Value = v }));