To fix the issue, I made a simple context menu item, saved to /usr/share/kde4/services/ServiceMenus/remote_extract.desktop
[Desktop Entry] Type=Service ServiceTypes=KonqPopupMenu/Plugin MimeType=application/x-tar;application/x-compressed-tar; application/x-bzip-compressed-tar;application/x-tarz; application/x-xz-compressed-tar;application/x-lzma-compressed-tar; application/x-deb;application/x-cd-image;application/x-bcpio; application/x-cpio;application/x-cpio-compressed;application/x-sv4cpio; application/x-sv4crc;application/x-rpm;application/x-servicepack; application/x-rar;application/x-7z-compressed;application/x-java-archive; application/zip;application/x-compress;application/x-gzip;application /x-bzip;application/x-bzip2;application/x-lzma;application/x-xz; application/lha;application/x-lha;application/maclha; Actions=extractRemote [Desktop Action extractRemote] Name=Extract Archive on Host Icon=utilities-file-archiver Exec=ssh user@host 'cd `dirname %f`;ark --batch --autodestination --autosubfolder "%f"'
The above assumes that the files have the same path on both machines. If this is not the case for you, a simple lookup table could be implemented in a bash script, and called in the Exec line. You'll also want to have key based SSH access, so you don't need to input your password. If the remote machine doesn't have ark installed, you could replace the ark call with unrar, unzip, etc.
The [Desktop Entry] section is used to specify the mimetypes the context menu is valid for, and specifies the action associated with the menu.
The [Desktop Action] section specifies the name used when rendering the menu, the icon that appears next to the name, and the Exec line. The Exec line ssh's to the remote host, cd's to the directory of the file that was selected, and runs ark's "extract here, autodetect subfolder" option.
See the freedesktop.org standards for more information about the Exec line and the variables available.