Taxis after Shabbos

I distinctly remember as a teenager borrowing a sefer one Shabbos in shul from a friend who was always carrying around aharonim. Probably the first time I ever looked in a book of responsa, I came across the following issue. I stumbled upon it this Shabbos while looking for something else, and it brought back memories.

Here is the question: Can an observant Jew utilize the services of a non-observant Jew who has not ended Shabbos by reciting either the full havdalah or even the short blessing of "ha-mavdil bein kodesh le-hol"? If a Jew has not ceremonially ended Shabbos, then he may not do any work. If so, an observant Jew may not ask him to do work. Therefore, may an observant Jew use a taxi on Saturday night? This is not only relevant in Israel, but also in Brooklyn and Queens where many car service drivers are Israeli or Russian.

The Tzitz Eliezer (11:34) demonstrates that the prohibition against work before reciting havdalah is not a rabbinic extension of Shabbos but an extension of havdalah. Just like one may not eat before praying in the morning, one may not perform labor before reciting havdalah. Therefore, argues the Tzitz Eliezer, someone who is non-observant and will not pray at all is certainly not prohibited from eating. The prohibition only applies to someone who plans on praying. Similarly, the prohibition against doing work after Shabbos is over but before havdalah only applies to someone who will eventually recite havdalah. It does not apply to someone who will not.

R. Moshe Shternbuch (Teshuvos Ve-Hanhagos, 2:161) writes similarly in the name of the Brisker Rav but also points out that the Vilna Gaon would disagree. Since, as indicated on the cover page of ever book of his, he is a descendant (nin ve-nekhed) of the Vilna Gaon, he feels obligated to pursue a line of reasoning that is consistent with this great sage's approach. He suggests that the prohibition is not like Shabbos, in which every act of forbidden work is an additional sin, but rather that once one performs labor before havdalah each additional act does not add to the violation. Therefore, since non-observant Jews have certainly already performed work after Shabbos but before havdalah, asking them to do more is not adding to their violation and is permissible.