Use a stored procedure.
The unique ID from a row (that represents a job) is what you want. If you're INNODB then you can just lock the row, if MyISAM then you'll need to lock the table, but in an SP it'd be lightening fast.
Essentially, your stored procedure would look like this (coming right out my a$$, haven't checked this):
procedure getOneRow()
BEGIN
declare tempID integer;
lock table mytable;
select id into tempID from mytable where fulfilled = 0;
update mytable set fulfilled=1 where id=tempID;
unlock table mytable;
select tempID;
END;
Then in PHP, particularly if you were using my dbConnection class, you would simply say:
$rowID = $db->singleAnswer('call getOneRow()');
This procedure could then be called from any number of processes from anywhere and you'd always get exactly 1 row that was unique and not in use by anyone else.