There are several ways of doing this. You can do it in AppleScript or a shell script, for example.
AppleScript tends to bog down if you try to process many files at once, but if you iterate through directories it shouldn't be a problem.
Shell scripts require more care to get right but will probably run faster on large directories - although you have to factor the script development time, which may have an impact.
Also, there are several ways of 'locking' a file. How the files are locked might have an impact - are they locked via the Finder's 'Get Info'? or some other method?
For a bare-bones AppleScript approach, this script will find all the locked files in a directory, save that list, then change the files to unlocked:
tell application "Finder"
-- get the list of files
set fileList to (every file of folder (choose folder) whose locked is true)
-- save the list
set saveFile to (open for access file ((path to desktop as text) & "locked files.out") with write permission)
write fileList to saveFile starting at 0
close access saveFile
-- now change the files
repeat with eachFile in fileList
set locked of eachFile to false
end repeat
end tell
Then you can reload the list and lock the files again:
tell application "Finder"
-- read the list of files
set fileList to read file ((path to desktop as text) & "locked files.out") as list
-- now lock each file
repeat with eachfile in fileList
set locked of eachfile to true
repeat
end tell
Note that the intermediate file is a binary file - you can't read it directly, but AppleScript can.
There's nothing in Leopard that will make this easier, either through shell or AppleScript.