Steve --

"...replaced the solenoid (under the radio compartment)..."

The solenoid is mounted on the tranny, but the OD relay sits among other relays behind the ashtray and fuse panel.

This sounds exactly like a relay that needs to be resoldered. You can do this yourself, and have NOTHING to lose by trying. $0, 15 minutes, no risk, clean 'n easy work. If it doesn't help, you've lost nothing.

BTW, while you're in there, resolder your fuel pump relay, too. That one can leave you stranded. Last year I towed wife's '91 740 home because it stalled on the road. It was the fuel pump relay, and two months later the same thing again happened but caused by the "radio suppression" relay.

Fix them before they fix you. I resoldered every relay I could find.

If, after you've resoldered, it's no better then you could have an intermittent solenoid (expensive and messy to replace). It could also be the tranny becoming varnished up -- my '86 245 (265k miles) is lazy shifting to OD on cold morning (below freezing), but it's only a 30-second lag. After it warms up it's fine for the day.

Wife's '91 740 (225k miles) shifts into OD fine and lock up works fine at 45 mph.