Some companies want a "scientist" type role with specialization in a particular area, say, physics or aerospace. But that never applies to computer science - CS doesn't really qualify you for a software engineering position, it just means you've studied the theory in depth.
In Europe a degree is a prerequisite for a high-end software engineering job, not so much in the US; I'd say perhaps 10% of companies in the private sector in the US actually require a degree, and most of those are in defense or in regulated industries such as medical devices or writing software for nuclear power plants. I'm aware of this because I lack even a bachelor's degree but have not had trouble finding well-paying software engineering jobs in the US.
Think about what the recruiter is looking for, assuming the recruiter is a technical manager or another software engineer; I want to know that you can do the job and hit the ground running. If it's an entry-level position with low salary, putting the PhD up there will indicate that your salary expectations are likely to be much higher. If it's not an entry-level position, the hiring manager will want to see in the first 5 seconds or so that you are already experienced in doing the job he or she is looking for.
Also job boards have become next to useless other than getting you on mailing lists for "URGENT JOB OPENING in Boise Idaho for person with 10+ years experience, pays up to $25/hr..." Some companies are still advertising jobs there but most good positions are hired through recruiters. Start with updating your resume and slant it toward experience rather than credentials. It's always good to spend time talking to recruiters once you've gotten the sense they're not the bottom-feeders who are looking for butts to fill seats. That's called networking...
The other thing that works against you is not being currently employed. It sounds really stupid but that's the reality: if you are already employed you are more desireable, if you are out of work some employers think it means there may be something wrong with you. Find a startup you'd like to work for then work on an open source project that requires the skills they want, then market your skills based on open source experience (with commits and projects on Github / SourceForge etc)