Конечно. Ведь 23 - это не "праздник мужчин", а праздник армии - притом конкретной страны. Не американской или камерунской, белорусской или афганской,  а советской (или вроде уже российской тоже). Так что если бы и поздравляла - то человека, имеющего отношение к РОССИЙСКРЙ армии - в том числе и женщину. Впрочем в совейское время задача облегчалась тем, что большинство парней или служили в армии, или имели отношение к ней (резерв, например).  Так Ваш кавалер служил в армии или нет? И как он воспринял Ваше поздравление и подарок? И вообще - он в курсе, что он "Ваш кавалер"?