Professor will not write a letter of recommendation because I have restricted access to my records under FERPA, is this legitimate?
David Z's comment is dead on: it is an unpleasant technicality that under FERPA regulations, one should not discuss the student's performance in any quantitatively specific way.  E.g., one should not say "Mr. X got an A in all my courses" or even "Mr. X was the top student in the course".  The exact rules are confusing to many faculty members, to the point where one feels like if one took FERPA too seriously one might not be able to write a suitable letter.

In my university there is, in theory, a form that a student can fill out to waive the FERPA regulations on a letter-by-letter basis.  In theory this means that if the letter is getting mailed to N institutions, one should fill out N forms.  

(The above considerations apply to all students, not just those who have asked for special protection.  However, a student who places further restrictions on their records is precisely going on the record as being especially concerned about their privacy, so in practice it makes a lot of sense to take the FERPA restrictions much more seriously for these students.)

It may or may not be the case that Dr. Z is himself trying to access or view any of your academic records.  (I guess he must have done something to find out that your records are FERPA-restricted though.)  Whether someone would look up a student's grades in courses taken by other faculty members must depend on the people and the institution.  For instance, at my institution I have access to the grades of all undergraduate students -- and I have been informed of the FERPA requirement that I access them only for legitimate, educational purposes -- but I do not have access to the grades of any graduate students, even my own advisees.  So in practice when I write letters for students I speak only about their performance in my courses -- but again, if they were FERPA-restricted and I was being suitably conscientious then I would even then have to be extremely careful about what I could say and likely be forbidden from including a certain amount of positive information about the student.

Also:


  I have no reason not to remove the FERPA restrictions, but I hate the thought of removing them under these circumstances; this tastes a little too much like blackmail to me.


Even assuming that Dr. Z wants permission to access your records and not just to talk about them, I think you are not viewing this in the right way.  "Blackmail" seems ridiculous to me: one of the conditions for that is that the blackmailer must have something to gain!  What does Dr. Z gain if you waive or even entirely remove your FERPA restrictions?  The pleasure of viewing some of your academic records?? 

For my part, I am curious as to why you chose to place restrictions on your academic records at all: what are you protecting yourself from, really?  It sounds like you may not completely understand what FERPA restrictions mean and may have just taken them on as a sort of free insurance.  If I were you I would learn more about this.  In my opinion, one could argue that "I have FERPA restricted my records" and "Please write me a strong recommendation letter" is already a bit of a mixed message.