Are state agencies subject to the the OASDI portion of FICA withholding on 414(h)(2) contributions?

It depends. If the 414(h)(2) contributions are taken out of the employee's salary, OASDI withholding (and payment of employer taxes) is required under section 3121(v). Otherwise, it is not.

Of course, this is in large part a matter of semantics. In practical terms, there is really little difference between stating the employee's salary as $100x, but then having a "salary reduction" of $5x and a corresponding employer contribution of $5x, and stating the employee's salary as $95 with a non-salary-reduction contribution of $5x.

Nevertheless, the semantics have a purpose. At least in social security states, the basis for the tax is the same as the basis for the ultimate social security benefits. The idea is to make sure that if the employer is reporting only $95x as social security wages at the time OASDI taxes are due, the employee should not later, when s/he claims benefits, be able to claim that the wages were $100x.

But what about the exception from the definition of employment contained in 3121(B)(7)? Does that mean that an instrumentality of a state would not have to withhold for the OASDI portion of FICA? I specify the OASDI portion because it appears that 3121(B)(7) is inapplicable to the Medicare portion of FICA pursuant to 3121(u)(2)(A). See PLR 9447044.

If the wages of an employee of a state or local government are exempt from the Social Security portion of OASDI, 414(h)(2) contributions will indeed be exempt from Social Security, also (although, as you correctly note, they will be subject to Medicare taxes). However, there are two major limitations on the application of the exemption in section 3121(B)(7):[list=1]
[*]Section 3121(B)(7)(E) excludes from that exemptionMost states (although not Pennsylvania) have entered into such agreements with respect to all of their employees. For a list of those which have not, see Section 1014 of the Social Security Handbook. Even those states may have entered into Section 128 agreements with respect to some of their political subdivisions.

[*]Section 3121(B)(7)(F) further excludes from that exemptionTreas. Reg. § 31.3121(B)(7)-2 interprets this rule to impose a requirement that employees must be covered by a retirement system that meets various minimum requirements before they can be exempt from Social Security coverage.[/list=1]Thus, the only employees of state and local government to whom section 3121(B)(7) applies are those (a) whose employment is not covered by a Section 218 agreement, and (B) who are personally covered by a retirement system meeting minimum requirements. If the employee is either (a) subject to a Section 218 agreement, or (B) covered by a retirement plan that requires section 414(h)(2) contributions, but does not meet minimum requirements under the regulation, the 414(h)(2) contributions are subject to Social Security taxes to the extent they reduce the employee's salary.

For more information on OASDI coverage of state and local government employees, see http://www.ssa.gov/slge/overview.htm.