A LR-32 Standard-Bluestrak headlamp relay works well for this application, too. It also has a built in fuse holder. I tend to agree with Fred. It's seems more like an issue in the solenoid, maybe it's grounded out internally?

Bill Burmeister