I need a method (software?) in which I can tell a Windows box to start a batch job from a Linux box.

Sort of like doing ssh with a script but this is having the Linux box tell windows to start a batch job.

IOW, we have a Linux CVS box that builds java applications. Then the application gets deployed/installed on the box Windows box.

I was thinking of having a Windows Task Schedule look for existence of a java on the Linux box, but how would I know Linux has finished modifying the file? I guess Linux could touch one last file and then we'd know to start the Windows job.

Yep, that's a classic soln to sync-ing 2 boxes when you can't do it from one program. I just use a signal/ctrl file eg ctrl.txt. That way it's generic, the target doesn't need to know what the last 'real' file is.
Just make sure the MS box deletes that that file.

Is telnet too basic?

But isn't telnet a security hole?

On our Win2k3 box I notice it's disabled.

Telnet is generally considered insecure because it transfers all data "in the clear", including passwords. On a completely local network, it might not be that bad.

One possible answer is to have samba on linux share out a drive (which the windows machines have mounted, or mount when they want to check), and it puts the files into there. Then you can have the windows machines look there and see if files exist. For one or two machines, this is probably not practical. But, if you have a number of windows machines, this might be easier than having the linux machine send to each one.