NOTE: there are a million stackoverflow answers explaining inserting into lookup fields that talk about __c fields. They are NOT duplicates of this question.
so I'm trying to insert a value into a lookup field using the rest api. If the field name looks like blah__c - it's easy - I just insert a {key, value} into blah__r. I do that all over the place.
but in this case my field is called PlanId. Trying to insert into PlanId__r just says no such field. How do I do it for a lookup field that does not end in __c?
You're talking about the insert/upsert by external id trick, right? Because vanilla lookup is absolutely the same, just chuck the 15/18-char id in. blah__c = '001...', PlanId = '003...'
For standard lookup field (without __c) most of the time the relation will be same thing minus the "Id" part. So try Plan = {'UniqueKey__c', '123'} or whatever is your equivalent.
(shameless plug) check my answer https://salesforce.stackexchange.com/a/274696/799, look at how that insert of Asset references Contact and Product2 even though the actual fields are ContactId, Product2Id.
https://salesforce.stackexchange.com/a/23507/799 might be helpful too. Or just use Workbench etc to describe your object.
There are few standard objects where upsert by external id won't work. You might have hard time adding Tasks to Accounts for example because that WhatId field is a mutant, lookup to many tables. Was few years since I tried that though so maybe something changed.