Following the example you give, using the memoir class, here is a simple way to implement what you want. Memoir may be a good option if you have precise, complex needs, because it is very comprehensive, especially for long documents.
Because memoir's \frontmatter, \mainmatter and friends alter the way section numbering is done, I suggest you create a whole new counter, since you are not really using it as a sectioning command anyway. If you need to add the paragraphs to the table of contents, it is possible too, so no worries there (just ask).
Here is the example document:
\documentclass{memoir}
% Load dummy text
\usepackage{lipsum}
% We create a counter
\newcounter{paracount}
% We create the paragraph command
\def\para{%
\refstepcounter{paracount}%
\noindent\textbf{\theparacount.\quad}}
% We create an index
\makeindex
% We tell memoir to index paragraphs and not pages
\renewcommand{\index}[1]{\specialindex{\jobname}{paracount}{#1}}
\begin{document}
\frontmatter
\para \index{Front matter entry} \lipsum[4]
\mainmatter
\para \index{First entry} \lipsum[1]
\para \index{Second entry} \lipsum[2]
\para \index{Third entry} \lipsum[3]
\printindex
\end{document}
Note that you can tell memoir to index things based on any counter, you just need to specify it in the \specialindex{\jobname}{<counter>}{#1} line.
Now, all you need to do is run LaTeX, then MakeIndex, then LaTeX again.
