First, I would take all those **`<p>` is more relevant for SEO than `<div>`** with a big grain of salt. SEO really only cares about content relevancy. Putting text in a `<div>` or in a `<p>` is not something you should be tweaking. Just go to what is the natural use.

`<div>` pretty much means 'this is a section of content' while `<p>` is 'this is a paragraph'. Personally, I just use `<div>` as it has no internal formatting in any browser, while `<p>` has some browser-specific formatting (margins, etc.) that can make things look different depending on the browser (unless you use a CSS 'cleaner').  Also, `<p>` inside `<div>` adds HTML which makes the pages a bit bigger, and thus, less pages would be crawled at once per crawler 'sweep'.

Worry about the content, not so much about how to write the HTML so search engines 'like it'.