In my app, user experience is better if more memory is used, so I have to decide if I really should free all the memory I can in didReceiveMemoryWarning. Based on Split's and Jasper Pol's answer, using a maximum of 45% of the total device memory appears to be a safe threshold (thanks guys).
In case someone wants to look at my actual implementation:
#import "mach/mach.h"
- (void)didReceiveMemoryWarning
{
    // Remember to call super
    [super didReceiveMemoryWarning];
    // If we are using more than 45% of the memory, free even important resources,
    // because the app might be killed by the OS if we don't
    if ([self __getMemoryUsedPer1] > 0.45)
    {
        // Free important resources here
    }
    // Free regular unimportant resources always here
}
- (float)__getMemoryUsedPer1
{
    struct mach_task_basic_info info;
    mach_msg_type_number_t size = sizeof(info);
    kern_return_t kerr = task_info(mach_task_self(), MACH_TASK_BASIC_INFO, (task_info_t)&info, &size);
    if (kerr == KERN_SUCCESS)
    {
        float used_bytes = info.resident_size;
        float total_bytes = [NSProcessInfo processInfo].physicalMemory;
        //NSLog(@"Used: %f MB out of %f MB (%f%%)", used_bytes / 1024.0f / 1024.0f, total_bytes / 1024.0f / 1024.0f, used_bytes * 100.0f / total_bytes);
        return used_bytes / total_bytes;
    }
    return 1;
}
Swift (based on this answer):
func __getMemoryUsedPer1() -> Float
{
    let MACH_TASK_BASIC_INFO_COUNT = (sizeof(mach_task_basic_info_data_t) / sizeof(natural_t))
    let name = mach_task_self_
    let flavor = task_flavor_t(MACH_TASK_BASIC_INFO)
    var size = mach_msg_type_number_t(MACH_TASK_BASIC_INFO_COUNT)
    var infoPointer = UnsafeMutablePointer<mach_task_basic_info>.alloc(1)
    let kerr = task_info(name, flavor, UnsafeMutablePointer(infoPointer), &size)
    let info = infoPointer.move()
    infoPointer.dealloc(1)
    if kerr == KERN_SUCCESS
    {
        var used_bytes: Float = Float(info.resident_size)
        var total_bytes: Float = Float(NSProcessInfo.processInfo().physicalMemory)
        println("Used: \(used_bytes / 1024.0 / 1024.0) MB out of \(total_bytes / 1024.0 / 1024.0) MB (\(used_bytes * 100.0 / total_bytes)%%)")
        return used_bytes / total_bytes
    }
    return 1
}